Submission #233348

#TimeUsernameProblemLanguageResultExecution timeMemory
233348MercenaryParachute rings (IOI12_rings)C++14
100 / 100
710 ms41592 KiB
#include<bits/stdc++.h> using namespace std; #define taskname "A" #define pb push_back #define mp make_pair typedef pair<int,int> ii; typedef long double ld; typedef long long ll; const int maxn = 1e6 + 5; int adj[maxn][2]; int n; struct G{ bitset<maxn> is_link; int lab[maxn]; int banned = -1; bool ok = 1; void init(int u){ banned = u; for(int i = 0 ; i < n ; ++i)lab[i] = -1; for(int i = 0 ; i < n ; ++i){ for(int j = 0 ; j < 2 ; ++j){ if(adj[i][j] != -1 && i > adj[i][j]){ Connect(i,adj[i][j]); } } } } int FindLab(int u){return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);} void Connect(int u , int v){ if(ok == 0 && banned != -1)return; if(u == banned)is_link[v] = 1; if(v == banned)is_link[u] = 1; if(u == banned || v == banned)return; u = FindLab(u);v = FindLab(v); if(u == v){ ok = 0; return; } if(lab[u] > lab[v])swap(u , v); lab[u] += lab[v]; lab[v] = u; } }a[4]; void Init(int _n){ memset(adj,-1,sizeof adj); n = _n; for(int i = 0 ; i < n ; ++i)a[0].lab[i] = -1; } int cycle = 0; int CurState = 0; int dfs(int u , int b){ int res = 1; int par = b; while(u != b){ res++; for(int i = 0 ; i < 2 ; ++i){ if(adj[u][i] != -1 && adj[u][i] != par){ par = u;u = adj[u][i]; break; } } } return res; } int deg[maxn]; void Link(int a , int b){ if(CurState == 4)return; if(deg[a] < deg[b])swap(a,b); deg[a]++;deg[b]++; if(CurState == 3){ for(int i = 0 ; i < 4 ; ++i){ ::a[i].Connect(a,b); if((a != ::a[i].banned && deg[a] - ::a[i].is_link[a] > 2) || (b != ::a[i].banned && deg[b] - ::a[i].is_link[b] > 2))::a[i].ok = 0; } return; } if(deg[a] == 3){ CurState = 3; for(int i = 0 ; i < 2 ; ++i){ ::a[i].init(adj[a][i]); } ::a[2].init(b); ::a[3].init(a); for(int i = 0 ; i < 4 ; ++i){ ::a[i].Connect(a,b); if((a != ::a[i].banned && deg[a] - ::a[i].is_link[a] > 2) || (b != ::a[i].banned && deg[b] - ::a[i].is_link[b] > 2)){ ::a[i].ok = 0; // cout << ::a[i].banned << endl; } } return; } for(int i = 0 ; i < 2 ; ++i){ if(adj[a][i] == -1){ adj[a][i] = b; break; } } for(int i = 0 ; i < 2 ; ++i){ if(adj[b][i] == -1){ adj[b][i] = a; break; } } if(::a[0].FindLab(a) == ::a[0].FindLab(b)){ if(CurState == 2)CurState = 4; else cycle = dfs(a , b) , CurState = 2; }else{ ::a[0].Connect(a , b); } } int CountCritical(){ if(CurState == 4)return 0; if(CurState == 3){ int res = 0; for(int i = 0 ; i < 4 ; ++i){ res += a[i].ok; } if(res == 0)CurState = 4; return res; } // cout << CurState << endl; if(CurState == 2)return cycle; return n; } #ifdef LOCAL #include <stdio.h> #include <stdlib.h> #include <assert.h> #define inbuf_len 1 << 16 #define outbuf_len 1 << 16 void Init(int N); int CountCritical(); void Link(int a, int b); int main() { freopen("A.INP","r",stdin); int tmp; /* Set input and output buffering */ char *inbuf, *outbuf; inbuf = (char*) malloc(inbuf_len * sizeof(char)); outbuf = (char*) malloc(outbuf_len * sizeof(char)); tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len); tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len); int N, L; tmp = scanf("%d %d", &N, &L); assert(tmp == 2); Init(N); int i; for (i = 0; i < L; i++) { int A, B; tmp = scanf("%d", &A); if (A == -1) { int critical; critical = CountCritical(); printf("%d\n", critical); } else { tmp = scanf("%d", &B); assert(tmp == 1); Link(A, B); } } return 0; } #endif // LOCAL
#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...