Submission #24150

#TimeUsernameProblemLanguageResultExecution timeMemory
24150HiasatParachute rings (IOI12_rings)C++14
0 / 100
2455 ms118608 KiB
#include <bits/stdc++.h> using namespace std; const int MX = 1000001; const int CHAIN = 0; const int CYCLE = 1; const int THREE = 2; const int BIG = 3; const int BLOCKED = 4; int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], pre[1000001], vsId, N; vector<int> adj[1000001]; bool block[1000001]; int res = 0,ff2[10]; bool ZERO = 0; int find(int u) { return dsu[u] == u ? u : dsu[u] = find(dsu[u]); } void Init(int N_) { N = N_; for (int i = 0; i < N; ++i) { dsu[i] = i; freq[i][0] = 1; pre[i] = 1; res += pre[i]; E[i] = 0; sz[i] = 1; ff2[0]++; } } bool fn(int u, int p) { if (vis[u] == vsId) { return false; } if (!block[u] && in[u] > 2) return false; vis[u] = vsId; for (int i = 0; i < adj[u].size(); ++i) { int v = adj[u][i]; if (v == p || block[v]) continue; if (block[u] && vis[v] == vsId) continue; if (!fn(v, u)) return false; } return true; } bool check(int u , int p) { block[u] = 1; vsId++; for (int i = 0; i < adj[u].size(); ++i) { in[adj[u][i]]--; } bool res = fn(u, p); for (int i = 0; i < adj[u].size(); ++i) { in[adj[u][i]]++; } block[u] = 0; return res; } void Link(int A, int B) { if (ZERO) return; adj[A].push_back(B); adj[B].push_back(A); if (type[find(A)] == BLOCKED || type[find(B)] == BLOCKED) return; /* if (find(A) == find(B) && (B == big[find(A)][4] || A == big[find(B)][4])) return;*/ freq[find(A)][in[A]]--; freq[find(B)][in[B]]--; in[A]++, in[B]++; in[A] = min(in[A], 4); in[B] = min(in[B], 4); freq[find(A)][in[A]]++; freq[find(B)][in[B]]++; res -= pre[find(A)]; ff2[type[find(A)]]--; if (find(A) != find(B)) { ff2[type[find(B)]]--; res -= pre[find(B)]; for (int i = 0 ; i <= 4 ; i++) { if (in[A] == i) { big[find(A)][i] = A; } if (in[B] == i) { big[find(B)][i] = B; } } E[find(B)] += E[find(A)]; sz[find(B)] += sz[find(A)]; for (int i = 0; i <= 4; ++i) { big[find(B)][i] = max(big[find(B)][i], big[find(A)][i]); freq[find(B)][i] += freq[find(A)][i]; } dsu[find(A)] = find(B); } E[find(B)]++; if (freq[find(A)][4] > 1 || freq[find(A)][3] > 4) { type[find(A)] = BLOCKED; ZERO = 1; } else if (freq[find(A)][4]) { type[find(A)] = BIG; pre[find(A)] = 0; if (check(big[find(A)][4], -1)) { pre[find(A)]++; } res += pre[find(A)]; } else if (freq[find(A)][3]) { type[find(A)]= THREE; pre[find(A)] = 0; if(check(big[find(A)][3],-1)) pre[find(A)]++; for (int j = 0 ; j < adj[big[find(A)][3]].size(); j++) { int v = adj[big[find(A)][3]][j]; if (check(v, -1)) { pre[find(A)]++; } } res += pre[find(A)]; } else { if (freq[find(A)][2] == sz[find(A)]) { type[find(A)] = CYCLE; } pre[find(A)] = sz[find(A)]; res += pre[find(A)]; } ff2[type[find(A)]]++; last[type[find(A)]] = find(A); } int CountCritical() { if (ZERO) return 0; int fn = 0; for (int i = 1; i <= 3; ++i){ fn += type[i]; } if(fn > 1) return 0; for (int i = 1; i <= 3; ++i){ if(ff2[i]){ return pre[last[i]]; } } return res; }

Compilation message (stderr)

rings.cpp: In function 'bool fn(int, int)':
rings.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < adj[u].size(); ++i) {
                  ~~^~~~~~~~~~~~~~~
rings.cpp: In function 'bool check(int, int)':
rings.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < adj[u].size(); ++i) {
                  ~~^~~~~~~~~~~~~~~
rings.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < adj[u].size(); ++i) {
                  ~~^~~~~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:120:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0 ; j < adj[big[find(A)][3]].size(); j++) {
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...