数组都开大了,栈也换手写了,自己造的极限数据也卡不掉,一交就 RE,怎么回事啊
#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std;
const int N = 2e5;
const int maxn = 1e6 + 10;
const int maxm = 3e6 + 10;
inline int read() {
int x = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch ^ 48);
ch = getchar();
}
return x;
}
struct Edge {
int to, next;
} ed[maxm];
int first[maxn], en = 1;
inline void insert(int x, int y) {
ed[en].to = y;
ed[en].next = first[x];
first[x] = en++;
}
int times, scc_cnt;
int dfn[maxn];
int low[maxn];
int sccid[maxn];
int scc_size[maxn];
struct stack {
int a[maxn], tp;
stack() {tp = 0;}
void push(int x) {a[++tp] = x;}
void pop() {if (tp) tp--;}
int top() {return a[tp];}
} s;
//stack<int> s;
void Tarjan(int now) {
s.push(now);
dfn[now] = low[now] = ++times;
for (int i = first[now]; i; i = ed[i].next) {
int v = ed[i].to;
if (!dfn[v]) {
Tarjan(v);
low[now] = min(low[now], low[v]);
} else if (!sccid[v]) {
low[now] = min(low[now], dfn[v]);
}
}
if (dfn[now] == low[now]) {
scc_cnt++;
scc_size[scc_cnt] = 0;
while (true) {
int x = s.top(); s.pop();
sccid[x] = scc_cnt;
scc_size[scc_cnt]++;
if (x == now) break;
}
}
}
void init() {
memset(ed, 0, sizeof(ed));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(sccid, 0, sizeof(sccid));
memset(first, 0, sizeof(first));
memset(scc_size, 0, sizeof(scc_size));
en = 1, s.tp = scc_cnt = times = 0;
}
int main() {
// freopen("data.txt", "r", stdin);
// freopen("b.txt", "w", stdout);
int T = read();
while (T--) {
init();
int n = read(), Max = 0;
for (int i = 1; i <= n; i++) {
int w = read(); insert(w, i + N);
Max = max(Max, w);
}
for (int i = 1; i <= n; i++) {
int e = read(); insert(i + N, e);
for (int j = e; j <= Max; j += e) {
insert(e, j);
}
}
for (int i = 1; i <= n; i++) {
if (!dfn[i + N]) Tarjan(i + N);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans += (scc_size[sccid[i + N]] > 1);
}
cout << ans << '\n';
}
return 0;
}