/**
* Prof.Nicola
**/
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define mp make_pair
#define F first
#define S second
#define REP(i,l,r) for(long long i=(l);i<(r);i++)
#define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--)
#define bitl __builtin_clz
#define bitr __builtin_ctz
#define bits __builtin_popcount
const long dx[4]={1,0,-1,0},dz[4]={0,1,0,-1};
const long double pi=3.14159265359;
const long long mod=1e9+7;
long long p(long long x){while(x&(x-1)){x=x&(x-1);}return x;}
long long squared(long long x){return (x*x)%mod;}
long long power(long long x,long long p){if(p==0){return 1;}if(p%2==1){return (power(x,p-1)*x)%mod;}return squared(power(x,p/2));}
long long inv(long long x){return power(x,mod-2);}
long long log(long long x,long long z){if(x<z){return 0;}return 1+log(x/z,z);}
template<class T>void re(T&x){cin>>x;}
template<class T1,class T2> void re(pair<T1,T2>&x){re(x.first);re(x.second);}
template<class T>void re(vector<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void re(deque<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void out(T x){cout<<x<<" ";}
template<class T1,class T2>void out(pair<T1,T2>x){out(x.first);out(x.second);cout<<endl;}
template<class T>void out(vector<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>void out(deque<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>void out(set<T>x){while(!x.empty()){out(*x.begin());x.erase(*x.begin());}cout<<endl;}
template<class T1,class T2>void out(map<T1,T2>x){while(!x.empty()){out(*x.begin());x.erase(x.begin()->first);}cout<<endl;}
template<class T>void out(queue<T>x){while(!x.empty()){out(x.front());x.pop();}cout<<endl;}
template<class T>void out(priority_queue<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;}
template<class T>void out(stack<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;}
template<class T>T cross(complex<T>x,complex<T>z){return (conj(x)*z).imag();}
template<class T>T dot(complex<T>x,complex<T>z){return (conj(x)*z).real();}
set<long long>::iterator T;
long long vLE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<=x){l+=z;}z/=2;}return l;}
long long vL(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<x){l+=z;}z/=2;}return l;}
long long vGE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return l;}l=vL(x,VT,l,r);if(l==r){return -1;}return l+1;}
long long vG(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return l;}l=vLE(x,VT,l,r);if(l==r){return -1;}return l+1;}
long long sLE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.begin()>x){return -1;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;}
long long sL(long long x,set<long long>&ST){if(*ST.begin()>=x){return -1;}if(ST.count(x)){T=ST.find(x);T--;return *T;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;}
long long sGE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.rbegin()<x){return -1;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;}
long long sG(long long x,set<long long>&ST){if(*ST.rbegin()<=x){return -1;}if(ST.count(x)){T=ST.find(x);T++;return *T;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;}
long N;
vector<vector<long> >vis;
struct DSU
{
vector<long>parent,sz;
long find_set(long x)
{
if(parent[x]==x){
return x;
}
return parent[x]=find_set(parent[x]);
}
bool same(long x,long z)
{
return (find_set(x)==find_set(z));
}
void union_set(long x,long z)
{
x=find_set(x);
z=find_set(z);
if(x!=z){
if(sz[z]>sz[x]){
swap(x,z);
}
REP(i,0,N){
if(i==x||i==z){
continue;
}
vis[i][x]+=vis[i][z];
vis[x][i]+=vis[z][i];
}
parent[z]=x;
sz[x]+=sz[z];
sz[z]=0;
}
}
};
DSU d;
void initialize(int n) {
N=n;
d.parent.resize(n);
d.sz.resize(n);
vis.resize(n);
REP(i,0,n){
vis[i].resize(n);
REP(j,0,n){
vis[i][j]=1;
}
d.parent[i]=i;
d.sz[i]=1;
}
}
int hasEdge(int u, int v) {
u=d.find_set(u);
v=d.find_set(v);
if(vis[u][v]>1){
vis[u][v]--;
vis[v][u]--;
return 0;
}
d.union_set(u,v);
return 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
296 KB |
Output is correct |
9 |
Correct |
0 ms |
296 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
296 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
0 ms |
204 KB |
Output is correct |
24 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
300 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
0 ms |
204 KB |
Output is correct |
24 |
Correct |
0 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
0 ms |
204 KB |
Output is correct |
27 |
Correct |
0 ms |
204 KB |
Output is correct |
28 |
Correct |
0 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
0 ms |
300 KB |
Output is correct |
31 |
Correct |
1 ms |
204 KB |
Output is correct |
32 |
Correct |
0 ms |
208 KB |
Output is correct |
33 |
Correct |
0 ms |
204 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
1 ms |
332 KB |
Output is correct |
42 |
Correct |
1 ms |
332 KB |
Output is correct |
43 |
Correct |
1 ms |
308 KB |
Output is correct |
44 |
Correct |
1 ms |
332 KB |
Output is correct |
45 |
Correct |
2 ms |
332 KB |
Output is correct |
46 |
Correct |
1 ms |
332 KB |
Output is correct |
47 |
Correct |
1 ms |
332 KB |
Output is correct |
48 |
Correct |
1 ms |
388 KB |
Output is correct |
49 |
Correct |
1 ms |
332 KB |
Output is correct |
50 |
Correct |
1 ms |
332 KB |
Output is correct |
51 |
Correct |
1 ms |
332 KB |
Output is correct |
52 |
Correct |
1 ms |
312 KB |
Output is correct |
53 |
Correct |
1 ms |
332 KB |
Output is correct |
54 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
300 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
0 ms |
204 KB |
Output is correct |
24 |
Correct |
0 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
204 KB |
Output is correct |
28 |
Correct |
1 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
1 ms |
296 KB |
Output is correct |
31 |
Correct |
0 ms |
204 KB |
Output is correct |
32 |
Correct |
1 ms |
204 KB |
Output is correct |
33 |
Correct |
0 ms |
204 KB |
Output is correct |
34 |
Correct |
1 ms |
312 KB |
Output is correct |
35 |
Correct |
2 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
1 ms |
332 KB |
Output is correct |
42 |
Correct |
2 ms |
308 KB |
Output is correct |
43 |
Correct |
1 ms |
332 KB |
Output is correct |
44 |
Correct |
1 ms |
332 KB |
Output is correct |
45 |
Correct |
1 ms |
332 KB |
Output is correct |
46 |
Correct |
2 ms |
332 KB |
Output is correct |
47 |
Correct |
1 ms |
332 KB |
Output is correct |
48 |
Correct |
1 ms |
332 KB |
Output is correct |
49 |
Correct |
1 ms |
332 KB |
Output is correct |
50 |
Correct |
1 ms |
332 KB |
Output is correct |
51 |
Correct |
1 ms |
332 KB |
Output is correct |
52 |
Correct |
1 ms |
332 KB |
Output is correct |
53 |
Correct |
1 ms |
332 KB |
Output is correct |
54 |
Correct |
1 ms |
332 KB |
Output is correct |
55 |
Correct |
34 ms |
4124 KB |
Output is correct |
56 |
Correct |
37 ms |
4080 KB |
Output is correct |
57 |
Correct |
34 ms |
4088 KB |
Output is correct |
58 |
Correct |
35 ms |
4108 KB |
Output is correct |
59 |
Correct |
34 ms |
4144 KB |
Output is correct |
60 |
Correct |
34 ms |
4020 KB |
Output is correct |
61 |
Correct |
34 ms |
4048 KB |
Output is correct |
62 |
Correct |
34 ms |
4036 KB |
Output is correct |
63 |
Correct |
35 ms |
4036 KB |
Output is correct |
64 |
Correct |
32 ms |
4132 KB |
Output is correct |
65 |
Correct |
32 ms |
4052 KB |
Output is correct |
66 |
Correct |
35 ms |
4044 KB |
Output is correct |
67 |
Correct |
35 ms |
4036 KB |
Output is correct |
68 |
Correct |
35 ms |
4028 KB |
Output is correct |
69 |
Correct |
35 ms |
4084 KB |
Output is correct |
70 |
Correct |
34 ms |
4068 KB |
Output is correct |
71 |
Correct |
33 ms |
4032 KB |
Output is correct |
72 |
Correct |
34 ms |
4084 KB |
Output is correct |
73 |
Correct |
33 ms |
4036 KB |
Output is correct |
74 |
Correct |
34 ms |
4072 KB |
Output is correct |
75 |
Correct |
33 ms |
4036 KB |
Output is correct |
76 |
Correct |
81 ms |
9028 KB |
Output is correct |
77 |
Correct |
88 ms |
8984 KB |
Output is correct |
78 |
Correct |
79 ms |
8988 KB |
Output is correct |
79 |
Correct |
82 ms |
9024 KB |
Output is correct |
80 |
Correct |
84 ms |
9060 KB |
Output is correct |
81 |
Correct |
92 ms |
9140 KB |
Output is correct |
82 |
Correct |
108 ms |
9060 KB |
Output is correct |
83 |
Correct |
81 ms |
9052 KB |
Output is correct |
84 |
Correct |
85 ms |
9028 KB |
Output is correct |
85 |
Correct |
162 ms |
15608 KB |
Output is correct |
86 |
Correct |
171 ms |
15560 KB |
Output is correct |
87 |
Correct |
160 ms |
15560 KB |
Output is correct |
88 |
Correct |
163 ms |
15616 KB |
Output is correct |
89 |
Correct |
162 ms |
15720 KB |
Output is correct |
90 |
Correct |
154 ms |
15632 KB |
Output is correct |
91 |
Correct |
159 ms |
15576 KB |
Output is correct |
92 |
Correct |
159 ms |
15632 KB |
Output is correct |
93 |
Correct |
157 ms |
15540 KB |
Output is correct |
94 |
Correct |
397 ms |
31244 KB |
Output is correct |
95 |
Correct |
391 ms |
31448 KB |
Output is correct |
96 |
Correct |
397 ms |
31364 KB |
Output is correct |
97 |
Correct |
392 ms |
31188 KB |
Output is correct |
98 |
Correct |
393 ms |
31368 KB |
Output is correct |
99 |
Correct |
404 ms |
31456 KB |
Output is correct |
100 |
Correct |
379 ms |
31212 KB |
Output is correct |