#include <bits/stdc++.h>
using namespace std;
struct ufds{
vector<int> sz, par;
ufds(){}
ufds(int n): sz(n, 1), par(n){
iota(par.begin(), par.end(), 0);
}
int find(int a){
return par[a] == a ? a : par[a] = find(par[a]);
}
int unite(int a, int b){
a = find(a), b = find(b);
if(a == b) return 0;
if(sz[a] < sz[b]) swap(a, b);
par[b] = a;
sz[a] += sz[b];
return 1;
}
};
int tots = 0;
set<int> ans;
vector<vector<int>> g, tree;
vector<int> deg;
int n;
ufds ds;
int bad = 0;
int d4 = 0;
void Init(int N){
n = N;
g.resize(n);
tree.resize(n);
deg.resize(n);
for(int i = 0; i < n; i++){
ans.insert(i);
}
ds = ufds(n);
}
void proc(int a, int add = 1){
if(deg[a] == 4){
if(add){
d4++;
if(d4 == 2) bad = 1;
}
if(!ans.count(a)) ans = {};
else ans = {a};
}else if(deg[a] == 3){
set<int> nans;
if(ans.count(a)) nans.insert(a);
for(int u: g[a]){
if(ans.count(u)) nans.insert(u);
}
ans = nans;
}
}
int cyc = 0;
vector<int> path;
int dfs(int v, int p, int x){
path.push_back(v);
if(v == x) return 1;
for(int u: tree[v]) if(u != p){
if(dfs(u, v, x)) return 1;
}
path.pop_back();
return 0;
}
int dfs2(int v, vector<int> &vis, int p){
vis[v] = 2;
for(int u: g[v]){
if(!vis[u]){
if(dfs2(u, vis, v)) return 1;
}
else if(vis[u] == 2 && u != p){
return 1;
}
}
return 0;
}
int cancer = -1;
int CountCritical(){
tots++;
if(bad) return 0;
if(ans.size() == 0) return 0;
int tot = 0;
if(tots >= 99){
set<int> gds;
int cnts = 0;
for(int i = 0; i < n; i++){
cnts += deg[i] >= 3;
}
for(int v: ans){
int ok = 1;
int t = cnts - (deg[v] >= 3);
if(deg[v] != 2){
vector<int> vis(n);
vis[v] = 1;
for(int u: g[v]){
t -= (deg[u] == 3);
}
for(int i = 0; i < n; i++){
if(!vis[i] && dfs2(i, vis, -1)){
ok = 0;
}
}
}
ok &= (t == 0 || deg[v] == 2);
tot += ok;
if(ok) gds.insert(v);
}
if(tot == 0) bad = 1;
cancer = tot;
assert(gds == ans);
assert(tot == ans.size());
}
if(bad) return 0;
return ans.size();
}
void Link(int a, int b){
if(bad) return;
int res = ds.unite(a, b);
deg[a]++, deg[b]++;
g[a].push_back(b);
g[b].push_back(a);
proc(a), proc(b);
if(!res){
if(!cyc){
dfs(a, -1, b);
ans = {};
for(int x: path){
ans.insert(x);
}
for(int i = 0; i < n; i++){
proc(i);
}
cyc = 1;
}else{
if(ans.size() > 2) bad = 1;
return;
}
}else{
tree[a].push_back(b);
tree[b].push_back(a);
}
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from rings.cpp:1:
rings.cpp: In function 'int CountCritical()':
rings.cpp:122:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | assert(tot == ans.size());
| ~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
3 ms |
980 KB |
Output is correct |
3 |
Correct |
3 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
852 KB |
Output is correct |
6 |
Correct |
4 ms |
1364 KB |
Output is correct |
7 |
Correct |
1 ms |
820 KB |
Output is correct |
8 |
Correct |
3 ms |
980 KB |
Output is correct |
9 |
Correct |
3 ms |
1184 KB |
Output is correct |
10 |
Correct |
3 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
545 ms |
88172 KB |
Output is correct |
2 |
Correct |
1164 ms |
113104 KB |
Output is correct |
3 |
Correct |
380 ms |
107560 KB |
Output is correct |
4 |
Correct |
1380 ms |
169188 KB |
Output is correct |
5 |
Correct |
1391 ms |
172732 KB |
Output is correct |
6 |
Correct |
1675 ms |
200116 KB |
Output is correct |
7 |
Correct |
390 ms |
108172 KB |
Output is correct |
8 |
Correct |
1290 ms |
153068 KB |
Output is correct |
9 |
Correct |
1398 ms |
167840 KB |
Output is correct |
10 |
Correct |
1036 ms |
165428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
3 ms |
980 KB |
Output is correct |
3 |
Correct |
3 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
852 KB |
Output is correct |
6 |
Correct |
4 ms |
1364 KB |
Output is correct |
7 |
Correct |
1 ms |
820 KB |
Output is correct |
8 |
Correct |
3 ms |
980 KB |
Output is correct |
9 |
Correct |
3 ms |
1184 KB |
Output is correct |
10 |
Correct |
3 ms |
1108 KB |
Output is correct |
11 |
Incorrect |
3 ms |
1108 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
3 ms |
980 KB |
Output is correct |
3 |
Correct |
3 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
852 KB |
Output is correct |
6 |
Correct |
4 ms |
1364 KB |
Output is correct |
7 |
Correct |
1 ms |
820 KB |
Output is correct |
8 |
Correct |
3 ms |
980 KB |
Output is correct |
9 |
Correct |
3 ms |
1184 KB |
Output is correct |
10 |
Correct |
3 ms |
1108 KB |
Output is correct |
11 |
Incorrect |
3 ms |
1108 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
3 ms |
980 KB |
Output is correct |
3 |
Correct |
3 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
852 KB |
Output is correct |
6 |
Correct |
4 ms |
1364 KB |
Output is correct |
7 |
Correct |
1 ms |
820 KB |
Output is correct |
8 |
Correct |
3 ms |
980 KB |
Output is correct |
9 |
Correct |
3 ms |
1184 KB |
Output is correct |
10 |
Correct |
3 ms |
1108 KB |
Output is correct |
11 |
Correct |
545 ms |
88172 KB |
Output is correct |
12 |
Correct |
1164 ms |
113104 KB |
Output is correct |
13 |
Correct |
380 ms |
107560 KB |
Output is correct |
14 |
Correct |
1380 ms |
169188 KB |
Output is correct |
15 |
Correct |
1391 ms |
172732 KB |
Output is correct |
16 |
Correct |
1675 ms |
200116 KB |
Output is correct |
17 |
Correct |
390 ms |
108172 KB |
Output is correct |
18 |
Correct |
1290 ms |
153068 KB |
Output is correct |
19 |
Correct |
1398 ms |
167840 KB |
Output is correct |
20 |
Correct |
1036 ms |
165428 KB |
Output is correct |
21 |
Incorrect |
3 ms |
1108 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |