Submission #119229

#TimeUsernameProblemLanguageResultExecution timeMemory
119229ioilolcom낙하산 고리들 (IOI12_rings)C++14
20 / 100
4086 ms104196 KiB
#include <bits/stdc++.h> using namespace std; #define endl "\n" #define pii pair<int,int> #define x first #define y second typedef long long int ll; int N; const int M=1e6+7; set<int> adj[M]; int parent[M]; struct DSU { DSU(int n){ for(int i=0; i<N; i++) parent[i] = i; } inline int find(int a){ if(parent[a] != a) parent[a] = find(parent[a]); return parent[a]; } inline void merge(int a,int b){ int pa = find(a); int pb = find(b); parent[pa] = pb; } }; void Init(int N_) { N = N_; } vector<pii> edges; void Link(int A, int B) { adj[A].insert(B); adj[B].insert(A); edges.push_back({A,B}); } bool is(int l){ DSU dsu(N); int deg[N+1]; for(int i=0; i<N; i++) { deg[i]=0; } for(auto m:edges) { if(m.x==l||m.y==l) { continue; } if(dsu.find(m.x)==dsu.find(m.y)) { return 0; } dsu.merge(m.x,m.y); deg[m.x]++; deg[m.y]++; } for(int i=0; i<N; i++) { if(deg[i]>2) { return 0; } } return 1; } int CountCritical() { int ans=0; for(int x=0; x<N; x++) ans+=is(x); 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...