/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
class DSU //with range compression and union by subtree size
{
public:
ll N; ll CC;
vector<ll> p,siz;
ll d0, d1, d2, d3; vector<ll> deg;
DSU() {N=0;}
DSU(ll n)
{
N=n; REP(i,0,N) {p.pb(i); siz.pb(1);}
d0=N; d1=0; d2=0; d3=0;VV(deg,N,0);
CC=N;
}
ll find(ll x)
{
if(p[x]==x) {return x;}
ll ans=find(p[x]);
p[x]=ans;
return ans;
}
void unionn(ll a, ll b)
{
deg[a]++; deg[b]++;
if(deg[a]==1) {d1++; d0--;} else if(deg[a]==2) {d2++; d1--;} else if(deg[a]==3) {d3++; d2--;}
if(deg[b]==1) {d1++; d0--;} else if(deg[b]==2) {d2++; d1--;} else if(deg[b]==3) {d3++; d2--;}
a=find(a); b=find(b);
if(a==b) {return;}
CC--;
if(siz[a]>siz[b]) {swap(a,b);}
p[a]=b; siz[b]+=siz[a];
}
ll EquivalenceClass(ll A) //O(N)
{
vector<ll> rep; VV(rep,N,0);
REP(i,0,N) {rep[find(i)]++;}
return rep[find(A)];
}
};
ll N;
vector<vector<ll> > adj;
vector<ll> a; vector<DSU> D;
bool yet3;
DSU T; ll ed; ll C;
void Init(int N_)
{
N = N_; yet3=false; T = *(new DSU(N)); ed=0; C=-1; VV(adj,N,{});
}
DSU* Create_DSU(ll node)
{
DSU *D = (new DSU(N));
REP(i,0,N)
{
if(i==node) {continue;}
REP(j,0,adj[i].size())
{
if(adj[i][j]==node || i>adj[i][j]) {continue;}
(*D).unionn(i,adj[i][j]);
}
}
return (D);
}
void Add_Node(ll node)
{
yet3=true;
ll nei;
REP(i,-1,adj[node].size())
{
if(i==-1) {nei = node;} else {nei = adj[node][i];}
a.pb(nei); D.pb(*Create_DSU(nei));
}
}
void Link(int A, int B)
{
ed++;
if(C==-1 && adj[A].size()==1 && adj[B].size()==1 && T.find(A)==T.find(B))
{
C=T.EquivalenceClass(A);
}
adj[A].pb(B); adj[B].pb(A);
T.unionn(A,B);
if(!yet3 && adj[A].size()==3) {Add_Node(A);return;}
if(!yet3 && adj[B].size()==3) {Add_Node(B);return;}
REP(i,0,a.size())
{
if(a[i]==A || a[i]==B) {continue;}
D[i].unionn(A,B);
}
}
int CountCritical()
{
if(yet3)
{
ll ans=0;
REP(i,0,a.size())
{
//cout<<a[i]<<" "<<D[i].d0<<" "<<D[i].d1<<" "<<D[i].d2<<" "<<D[i].d3<<endl;
if(D[i].d3==0 && 2*(D[i].CC-D[i].d0)==D[i].d1) {ans++;}
}
return ans;
}
else
{
ll cyc = ed-(N-T.CC);
if(cyc>=2) {return 0;}
else if(cyc==0) {return N;}
else {return C;}
}
}
Compilation message
rings.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
5 | #pragma GCC optimization ("O3")
|
rings.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
6 | #pragma GCC optimization ("unroll-loops")
|
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
3 ms |
1184 KB |
Output is correct |
3 |
Correct |
3 ms |
1184 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
3 ms |
804 KB |
Output is correct |
7 |
Correct |
2 ms |
1156 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
3 ms |
1320 KB |
Output is correct |
10 |
Correct |
4 ms |
1312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
331 ms |
40972 KB |
Output is correct |
2 |
Correct |
1476 ms |
139152 KB |
Output is correct |
3 |
Correct |
1737 ms |
168568 KB |
Output is correct |
4 |
Correct |
940 ms |
86556 KB |
Output is correct |
5 |
Correct |
982 ms |
99928 KB |
Output is correct |
6 |
Correct |
959 ms |
98120 KB |
Output is correct |
7 |
Correct |
1662 ms |
180108 KB |
Output is correct |
8 |
Correct |
1722 ms |
176224 KB |
Output is correct |
9 |
Correct |
1797 ms |
189100 KB |
Output is correct |
10 |
Correct |
676 ms |
97392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
3 ms |
1184 KB |
Output is correct |
3 |
Correct |
3 ms |
1184 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
3 ms |
804 KB |
Output is correct |
7 |
Correct |
2 ms |
1156 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
3 ms |
1320 KB |
Output is correct |
10 |
Correct |
4 ms |
1312 KB |
Output is correct |
11 |
Correct |
4 ms |
1312 KB |
Output is correct |
12 |
Correct |
7 ms |
2260 KB |
Output is correct |
13 |
Correct |
7 ms |
2264 KB |
Output is correct |
14 |
Correct |
5 ms |
2004 KB |
Output is correct |
15 |
Correct |
5 ms |
3684 KB |
Output is correct |
16 |
Correct |
4 ms |
1236 KB |
Output is correct |
17 |
Correct |
5 ms |
2260 KB |
Output is correct |
18 |
Correct |
9 ms |
3684 KB |
Output is correct |
19 |
Correct |
4 ms |
1364 KB |
Output is correct |
20 |
Correct |
7 ms |
2260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
3 ms |
1184 KB |
Output is correct |
3 |
Correct |
3 ms |
1184 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
3 ms |
804 KB |
Output is correct |
7 |
Correct |
2 ms |
1156 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
3 ms |
1320 KB |
Output is correct |
10 |
Correct |
4 ms |
1312 KB |
Output is correct |
11 |
Correct |
4 ms |
1312 KB |
Output is correct |
12 |
Correct |
7 ms |
2260 KB |
Output is correct |
13 |
Correct |
7 ms |
2264 KB |
Output is correct |
14 |
Correct |
5 ms |
2004 KB |
Output is correct |
15 |
Correct |
5 ms |
3684 KB |
Output is correct |
16 |
Correct |
4 ms |
1236 KB |
Output is correct |
17 |
Correct |
5 ms |
2260 KB |
Output is correct |
18 |
Correct |
9 ms |
3684 KB |
Output is correct |
19 |
Correct |
4 ms |
1364 KB |
Output is correct |
20 |
Correct |
7 ms |
2260 KB |
Output is correct |
21 |
Correct |
18 ms |
4096 KB |
Output is correct |
22 |
Correct |
36 ms |
6156 KB |
Output is correct |
23 |
Correct |
39 ms |
7772 KB |
Output is correct |
24 |
Correct |
69 ms |
15876 KB |
Output is correct |
25 |
Correct |
25 ms |
16056 KB |
Output is correct |
26 |
Correct |
72 ms |
17684 KB |
Output is correct |
27 |
Correct |
56 ms |
8280 KB |
Output is correct |
28 |
Correct |
82 ms |
16756 KB |
Output is correct |
29 |
Correct |
53 ms |
16756 KB |
Output is correct |
30 |
Correct |
57 ms |
10116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
3 ms |
1184 KB |
Output is correct |
3 |
Correct |
3 ms |
1184 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
3 ms |
804 KB |
Output is correct |
7 |
Correct |
2 ms |
1156 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
3 ms |
1320 KB |
Output is correct |
10 |
Correct |
4 ms |
1312 KB |
Output is correct |
11 |
Correct |
331 ms |
40972 KB |
Output is correct |
12 |
Correct |
1476 ms |
139152 KB |
Output is correct |
13 |
Correct |
1737 ms |
168568 KB |
Output is correct |
14 |
Correct |
940 ms |
86556 KB |
Output is correct |
15 |
Correct |
982 ms |
99928 KB |
Output is correct |
16 |
Correct |
959 ms |
98120 KB |
Output is correct |
17 |
Correct |
1662 ms |
180108 KB |
Output is correct |
18 |
Correct |
1722 ms |
176224 KB |
Output is correct |
19 |
Correct |
1797 ms |
189100 KB |
Output is correct |
20 |
Correct |
676 ms |
97392 KB |
Output is correct |
21 |
Correct |
4 ms |
1312 KB |
Output is correct |
22 |
Correct |
7 ms |
2260 KB |
Output is correct |
23 |
Correct |
7 ms |
2264 KB |
Output is correct |
24 |
Correct |
5 ms |
2004 KB |
Output is correct |
25 |
Correct |
5 ms |
3684 KB |
Output is correct |
26 |
Correct |
4 ms |
1236 KB |
Output is correct |
27 |
Correct |
5 ms |
2260 KB |
Output is correct |
28 |
Correct |
9 ms |
3684 KB |
Output is correct |
29 |
Correct |
4 ms |
1364 KB |
Output is correct |
30 |
Correct |
7 ms |
2260 KB |
Output is correct |
31 |
Correct |
18 ms |
4096 KB |
Output is correct |
32 |
Correct |
36 ms |
6156 KB |
Output is correct |
33 |
Correct |
39 ms |
7772 KB |
Output is correct |
34 |
Correct |
69 ms |
15876 KB |
Output is correct |
35 |
Correct |
25 ms |
16056 KB |
Output is correct |
36 |
Correct |
72 ms |
17684 KB |
Output is correct |
37 |
Correct |
56 ms |
8280 KB |
Output is correct |
38 |
Correct |
82 ms |
16756 KB |
Output is correct |
39 |
Correct |
53 ms |
16756 KB |
Output is correct |
40 |
Correct |
57 ms |
10116 KB |
Output is correct |
41 |
Correct |
209 ms |
35924 KB |
Output is correct |
42 |
Correct |
777 ms |
143476 KB |
Output is correct |
43 |
Correct |
368 ms |
146888 KB |
Output is correct |
44 |
Correct |
1248 ms |
170648 KB |
Output is correct |
45 |
Correct |
1236 ms |
170100 KB |
Output is correct |
46 |
Correct |
667 ms |
82936 KB |
Output is correct |
47 |
Correct |
844 ms |
85372 KB |
Output is correct |
48 |
Correct |
821 ms |
164156 KB |
Output is correct |
49 |
Correct |
663 ms |
83208 KB |
Output is correct |
50 |
Correct |
706 ms |
82112 KB |
Output is correct |
51 |
Correct |
440 ms |
128456 KB |
Output is correct |
52 |
Correct |
1067 ms |
136988 KB |
Output is correct |
53 |
Correct |
837 ms |
164300 KB |
Output is correct |
54 |
Correct |
1536 ms |
151300 KB |
Output is correct |
55 |
Correct |
1694 ms |
163988 KB |
Output is correct |