#include<bits/stdc++.h>
#pragma("03")
using namespace std;
#define pii pair<int, int>
int N;
vector<vector<int>> adj;
vector<bool> passed;
set<pii> m;
vector<int> oc;
void Init(signed N_) {
N = N_;
oc.resize(5);
adj.resize(N);
passed.resize(N, false);
for(int i= 0; i<N; i++){
m.insert({0, i});
oc[0]++;
}
}
int flored(int id){
return min(4, id);
}
void Link(signed A, signed B) {
/*m.erase({adj[A].size(), A});
m.erase({adj[B].size(), B});*/
oc[flored(adj[A].size())]--;
oc[flored(adj[B].size())]--;
adj[A].push_back(B);
adj[B].push_back(A);
oc[flored(adj[A].size())]++;
oc[flored(adj[B].size())]++;
//m.insert({adj[B].size(), B});
}
int forbiden = 0;
bool acyclic = true;
void dfs(int id, int anc){
passed[id] = true;
for(auto v: adj[id]){
if(v!=forbiden && v!=anc){
if(passed[v]){
acyclic = false;
}
else{
dfs(v, id);
}
}
}
}
bool test_crititcal(int id){
forbiden = id;
for(int i = 0; i<N; i++){
int deg =0;
if(i == id){
continue;
}
for(auto e: adj[i]){
if(e!=id){
deg++;
}
}
if(deg>2){
////cout<<"deg "<<endl;
return false;
}
}
fill(passed.begin(), passed.end(), false);
acyclic = true;
for(int i= 0; i<N; i++){
if(!passed[i] && i!=forbiden){
dfs(i, -1);
}
}
return acyclic;
}
int nbc = 0;
void nb_cycles(int u, int prev){
passed[u] = true;
for(auto v: adj[u]){
if(v==prev){
continue;
}
if(passed[v]){
nbc++;
//cout<<u<<" "<<v<<endl;
}
else{
nb_cycles(v, u);
}
}
}
pair<bool, int> find_single(int u, int a, set<int>& s){
passed[u] = true;
for(auto v: adj[u]){
if(v!=a){
if(passed[v]){
s.insert(u);
return {true, v};
}
else{
auto res = find_single(v, u, s);
if(res.second == u){
s.insert(u);
return {false, -1};
}
else{
if(res.first){
s.insert(u);
return res;
}
}
}
}
}
return {false, -1};
}
void calc_cycles(set<int>& ok){
fill(passed.begin(), passed.end(), 0);
nbc= 0;
for(int i = 0; i<N; i++){
if(!passed[i]){
nb_cycles(i,-1);
}
}
nbc/=2;
}
void find_ok_first(set<int>& ok){
/*cout<<"ok "<<endl;
for(auto e: ok){
cout<<e<<" ";
}
cout<<endl;*/
}
signed CountCritical() {
m.clear();
for(int i = 0; i<N; i++){
m.insert({adj[i].size(), i});
}
int res= 0;
if(oc[4]>1){
return 0;
}
else if(oc[4] == 1){
int cand = m.lower_bound({4, 0})->second;
if(test_crititcal(cand)){
res++;
}
return res;
}
else{
set<int> ok;
calc_cycles(ok);
if(nbc==1){
fill(passed.begin(), passed.end(), 0);
for(int i = 0; i<N; i++){
if(!passed[i]){
find_single(i,-1, ok);
}
}
}
if(oc[3]>0){
auto it = m.lower_bound({3, 0});
vector<int> off(N);
for(; it!=m.end(); ++it){
set<int> neigs;
for(auto e: adj[it->second]){
off[e]++;
}
off[it->second]++;
}
set<int> pass;
for(int i = 0; i<N; i++){
if(off[i] == oc[3]){
if(test_crititcal(i)){
pass.insert(i);
}
}
}
return pass.size();
}
else if(nbc==0){
return N;
}
return ok.size();
}
}
Compilation message
rings.cpp:2: warning: ignoring '#pragma ( ' [-Wunknown-pragmas]
2 | #pragma("03")
|
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
860 KB |
Output is correct |
3 |
Correct |
3 ms |
860 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
860 KB |
Output is correct |
6 |
Correct |
3 ms |
1372 KB |
Output is correct |
7 |
Correct |
1 ms |
660 KB |
Output is correct |
8 |
Correct |
2 ms |
860 KB |
Output is correct |
9 |
Correct |
3 ms |
856 KB |
Output is correct |
10 |
Correct |
4 ms |
856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
474 ms |
53396 KB |
Output is correct |
2 |
Correct |
1033 ms |
83284 KB |
Output is correct |
3 |
Correct |
1040 ms |
110936 KB |
Output is correct |
4 |
Correct |
1645 ms |
116308 KB |
Output is correct |
5 |
Correct |
1640 ms |
118124 KB |
Output is correct |
6 |
Correct |
1950 ms |
167020 KB |
Output is correct |
7 |
Correct |
1070 ms |
109836 KB |
Output is correct |
8 |
Correct |
1892 ms |
112152 KB |
Output is correct |
9 |
Correct |
1727 ms |
120256 KB |
Output is correct |
10 |
Correct |
1074 ms |
116824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
860 KB |
Output is correct |
3 |
Correct |
3 ms |
860 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
860 KB |
Output is correct |
6 |
Correct |
3 ms |
1372 KB |
Output is correct |
7 |
Correct |
1 ms |
660 KB |
Output is correct |
8 |
Correct |
2 ms |
860 KB |
Output is correct |
9 |
Correct |
3 ms |
856 KB |
Output is correct |
10 |
Correct |
4 ms |
856 KB |
Output is correct |
11 |
Correct |
33 ms |
964 KB |
Output is correct |
12 |
Correct |
101 ms |
1388 KB |
Output is correct |
13 |
Correct |
124 ms |
1316 KB |
Output is correct |
14 |
Correct |
81 ms |
1332 KB |
Output is correct |
15 |
Correct |
193 ms |
2132 KB |
Output is correct |
16 |
Correct |
98 ms |
1308 KB |
Output is correct |
17 |
Correct |
102 ms |
1360 KB |
Output is correct |
18 |
Correct |
188 ms |
2440 KB |
Output is correct |
19 |
Correct |
110 ms |
1560 KB |
Output is correct |
20 |
Correct |
120 ms |
1364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
860 KB |
Output is correct |
3 |
Correct |
3 ms |
860 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
860 KB |
Output is correct |
6 |
Correct |
3 ms |
1372 KB |
Output is correct |
7 |
Correct |
1 ms |
660 KB |
Output is correct |
8 |
Correct |
2 ms |
860 KB |
Output is correct |
9 |
Correct |
3 ms |
856 KB |
Output is correct |
10 |
Correct |
4 ms |
856 KB |
Output is correct |
11 |
Correct |
33 ms |
964 KB |
Output is correct |
12 |
Correct |
101 ms |
1388 KB |
Output is correct |
13 |
Correct |
124 ms |
1316 KB |
Output is correct |
14 |
Correct |
81 ms |
1332 KB |
Output is correct |
15 |
Correct |
193 ms |
2132 KB |
Output is correct |
16 |
Correct |
98 ms |
1308 KB |
Output is correct |
17 |
Correct |
102 ms |
1360 KB |
Output is correct |
18 |
Correct |
188 ms |
2440 KB |
Output is correct |
19 |
Correct |
110 ms |
1560 KB |
Output is correct |
20 |
Correct |
120 ms |
1364 KB |
Output is correct |
21 |
Execution timed out |
4051 ms |
4524 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
860 KB |
Output is correct |
3 |
Correct |
3 ms |
860 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
860 KB |
Output is correct |
6 |
Correct |
3 ms |
1372 KB |
Output is correct |
7 |
Correct |
1 ms |
660 KB |
Output is correct |
8 |
Correct |
2 ms |
860 KB |
Output is correct |
9 |
Correct |
3 ms |
856 KB |
Output is correct |
10 |
Correct |
4 ms |
856 KB |
Output is correct |
11 |
Correct |
474 ms |
53396 KB |
Output is correct |
12 |
Correct |
1033 ms |
83284 KB |
Output is correct |
13 |
Correct |
1040 ms |
110936 KB |
Output is correct |
14 |
Correct |
1645 ms |
116308 KB |
Output is correct |
15 |
Correct |
1640 ms |
118124 KB |
Output is correct |
16 |
Correct |
1950 ms |
167020 KB |
Output is correct |
17 |
Correct |
1070 ms |
109836 KB |
Output is correct |
18 |
Correct |
1892 ms |
112152 KB |
Output is correct |
19 |
Correct |
1727 ms |
120256 KB |
Output is correct |
20 |
Correct |
1074 ms |
116824 KB |
Output is correct |
21 |
Correct |
33 ms |
964 KB |
Output is correct |
22 |
Correct |
101 ms |
1388 KB |
Output is correct |
23 |
Correct |
124 ms |
1316 KB |
Output is correct |
24 |
Correct |
81 ms |
1332 KB |
Output is correct |
25 |
Correct |
193 ms |
2132 KB |
Output is correct |
26 |
Correct |
98 ms |
1308 KB |
Output is correct |
27 |
Correct |
102 ms |
1360 KB |
Output is correct |
28 |
Correct |
188 ms |
2440 KB |
Output is correct |
29 |
Correct |
110 ms |
1560 KB |
Output is correct |
30 |
Correct |
120 ms |
1364 KB |
Output is correct |
31 |
Execution timed out |
4051 ms |
4524 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |