缩点 RE 求助,调了好几个小时了
查看原帖
缩点 RE 求助,调了好几个小时了
249422
TinyMirror1楼主2020/11/20 07:52

数组都开大了,栈也换手写了,自己造的极限数据也卡不掉,一交就 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;
}
2020/11/20 07:52
加载中...