QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#127706#1000. 边三连通分量1234567890#WA 4ms60888kbC++144.5kb2023-07-19 22:30:262023-07-19 22:30:28

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-19 22:30:28]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:60888kb
  • [2023-07-19 22:30:26]
  • 提交

answer

/*
灏忓簾鐗╋紝杩欓兘涓嶄細 /cf
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define mp make_pair
#define inf (ll)1e9
#define pii pair <ll, ll>
#define fr first
#define se second
const ll mod = 1e9 + 7;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 18, stdin), p1 == p2) ? EOF : *p1++)
inline ll read() {
	ll x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') f = ((ch == '-') ? -1 : f), ch = getchar();
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x * f;
}
inline void write(ll x) {
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}
ll n, m;
vector <pii> G[500005];
bool ban[500005];

const ll Mod = 11451411;
struct HashTable {
	ll sta[500005], top;
	ull to[500005];
	ll head[Mod+5], num[500005], nxt[500005], tot;
	inline ll val(ull x) {
		ll p = x % Mod;
		for(ll i = head[p]; i; i = nxt[i]) if(to[i] == x) return num[i];
		return 0;
	}
	inline void add(ull x, ll y) {
		ll p = x % Mod;
		for(ll i = head[p]; i; i = nxt[i]) {
			if(to[i] == x) {
				num[i] += y;
				return ;
			}
		}
		num[++tot] = y, to[tot] = x, nxt[tot] = head[p], head[p] = tot;
	}
	inline void clear() {
		tot = 0;
		while(top) head[sta[top--]] = 0;
	}
}H;

struct UnionSet {
	ll fa[500005];
	inline void makeSet(ll x) {
		for(ll i = 1; i <= x; i++) fa[i] = i;
	}
	inline ll findSet(ll x) {
		if(x == fa[x]) return x;
		return fa[x] = findSet(fa[x]);
	}
	inline void unionSet(ll x, ll y) {
		x = findSet(x), y = findSet(y);
		if(x == y) return ;
		fa[x] = y;
	}
}U;

ll dfn[500005], low[500005], tot;

inline void Tarjan(ll x, ll fa) {
	dfn[x] = low[x] = ++tot;
	for(auto y : G[x]) {
		if(y.se == fa) continue;
		if(!dfn[y.fr]) {
			Tarjan(y.fr, y.se);
			if(low[y.fr] > dfn[x]) ban[y.se] = 1;
			low[x] = min(low[x], low[y.fr]);
		} 
		else low[x] = min(low[x], dfn[y.fr]);
	}
}
inline void get_bri() {
	for(ll i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i, 0);
}

ll seq[500005], num;
vector <pii> Tr[500005], Bk[500005]; 
inline void dfs(ll x, ll fa) {
	dfn[x] = ++tot, seq[++num] = x;
	for(auto y : G[x]) {
		if(ban[y.se] || y.se == fa) continue;
		if(!dfn[y.fr]) {
			Tr[x].push_back(y);
			dfs(y.fr, y.se);
		}
		else if(dfn[x] > dfn[y.fr]) Bk[x].push_back(y);
	}
}
ull a[500005], b[500005];
inline void dfs2(ll x) {
	for(auto y : Tr[x]) {
		dfs2(y.fr);
		a[y.se] = b[y.fr], b[x] ^= b[y.fr];
	}
}
inline void solve() {
	srand(time(NULL));
	default_random_engine e(1ll * rand() * rand());
	uniform_int_distribution <ull> R(0, (1ull << 63) - 1);
	tot = 0;
	for(ll i = 1; i <= n; i++) dfn[i] = 0;
	for(ll i = 1; i <= n; i++) {
		if(!dfn[i]) {
			num = 0;
			dfs(i, 0);
			for(ll j = 1; j <= num; j++) for(auto k : Bk[seq[j]]) a[k.se] = R(e), b[seq[j]] ^= a[k.se], b[k.fr] ^= a[k.se];
			dfs2(i);
			
			H.clear();
			for(ll j = 1; j <= num; j++) {
				for(auto k : Bk[seq[j]]) H.add(a[k.se], 1);//, printf("! %lld\n", a[k.se]);
				for(auto k : Tr[seq[j]]) H.add(a[k.se], 1);//, printf("! %lld\n", a[k.se]);
			}
			for(ll j = 1; j <= num; j++) {
				for(auto k : Bk[seq[j]]) if(H.val(a[k.se]) > 1) ban[k.se] = 1;
				for(auto k : Tr[seq[j]]) if(H.val(a[k.se]) > 1) ban[k.se] = 1;
			} 
			
//			H.clear();
//			for(ll j = 1; j <= num; j++) for(auto k : Bk[seq[j]]) H.add(a[k.se], 1);
//			for(ll j = 1; j <= num; j++) for(auto k : Tr[seq[j]]) if(H.val(a[k.se]) >= 1) ban[k.se] = 1;
//			
//			H.clear();
//			for(ll j = 1; j <= num; j++) for(auto k : Tr[seq[j]]) H.add(a[k.se], 1);
//			for(ll j = 1; j <= num; j++) for(auto k : Bk[seq[j]]) if(H.val(a[k.se]) >= 1) ban[k.se] = 1;

			
		}
	}
}
ll cnt;
vector <ll> V[500005];
int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	n = read(), m = read();
	for(ll i = 1; i <= m; i++) {
		ll u = read(), v = read();
		G[u].push_back(mp(v, i));
		G[v].push_back(mp(u, i));
	}
	get_bri(), solve();
	U.makeSet(n);
	for(ll i = 1; i <= n; i++) for(auto j : G[i]) if(i > j.fr && !ban[j.se]) U.unionSet(i, j.fr);
	for(ll i = 1; i <= n; i++) V[U.findSet(i)].push_back(i), cnt += (U.findSet(i) == i);
	
//	for(ll i = 1; i <= m; i++) printf("?? %lld %lld %lld\n", i, a[i], ban[i]);
	write(cnt), putchar('\n');
	for(ll i = 1; i <= n; i++) {
		if(i != U.findSet(i)) continue;
		for(auto j : V[i]) write(j), putchar(' ');
		putchar('\n');
	}
	return 0;
}
/*
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 60888kb

input:

4 5
0 2
0 1
3 0
2 1
2 3

output:

2
3 
4 

result:

wrong answer Integer 4 violates the range [0, 3]