제출 #63107

#제출 시각아이디문제언어결과실행 시간메모리
63107reality낙하산 고리들 (IOI12_rings)C++17
100 / 100
1965 ms52628 KiB
#include "bits/stdc++.h" using namespace std; #define fi first #define se second #define ll long long #define dbg(v) cerr<<#v<<" = "<<v<<'\n' #define vi vector<int> #define vl vector <ll> #define pii pair<int,int> #define mp make_pair #define db long double #define pb push_back #define all(s) s.begin(),s.end() template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;} template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;} const int NN = 2e6 + 5; int n; int f[NN]; int deg[NN]; int sz[NN]; vector < pii > e; int ans; int gg[5][NN]; int dg[5][NN]; vi who; vi ANS; int szz; int cyc; int g(int w,int k) { return gg[w][k] == k ? k : gg[w][k] = g(w,gg[w][k]); } int get(int k) { return k == f[k] ? k : f[k] = get(f[k]); } void Init(int N_) { n = N_; ans = n; for (int i = 1;i <= n;++i) { f[i] = i,sz[i] = 1; } } void Link(int A, int B) { ++A;++B; e.pb(mp(A,B)); if (!szz && (deg[A] >= 2 || deg[B] >= 2)) { if (deg[A] < 2) swap(A,B); for (auto it : e) { if (it.fi == A) who.pb(it.se); else if (it.se == A) who.pb(it.fi); } who.pb(A); szz = who.size(); ANS = vi(szz,1); for (int i = 0;i < szz;++i) { for (int j = 1;j <= n;++j) gg[i][j] = j,dg[i][j] = 0; for (auto it : e) { if (it.fi == who[i] || it.se == who[i]) continue; int x = g(i,it.fi); int y = g(i,it.se); ++dg[i][it.fi]; ++dg[i][it.se]; ANS[i] &= dg[i][it.fi] <= 2 && dg[i][it.se] <= 2 && x != y; gg[i][x] = y; } } } else if (szz) { for (int i = 0;i < szz;++i) { if (A == who[i] || B == who[i]) continue; int x = g(i,A); int y = g(i,B); ++dg[i][A]; ++dg[i][B]; ANS[i] &= dg[i][A] <= 2 && dg[i][B] <= 2 && x != y; gg[i][x] = y; } } else { int x = get(A); int y = get(B); ++deg[A]; ++deg[B]; if (x == y) ++cyc,ans = (cyc == 1) * sz[x]; else { sz[y] += sz[x]; sz[x] = 0; f[x] = y; } } } int CountCritical() { if (szz) return accumulate(all(ANS),0); return ans; }
#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...