| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1043126 |
2024-08-04T00:44:45 Z |
wood |
Joker (BOI20_joker) |
C++17 |
|
1448 ms |
8136 KB |
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
struct dsu{
vector<bool> side;
vector<int> rep, size;
dsu(int n){
for(int i = 0; i<n; i++){
rep.pb(i);
side.pb(0);
size.pb(1);
}
}
int get(int u){
if(u == rep[u]) return u;
int oldparent = rep[u];
rep[u] = get(rep[u]);
side[u] = side[u]^side[oldparent];
return rep[u];
}
void merge(int u, int v){
int oldu = u, oldv = v;
u = get(u); v = get(v);
if(size[v]>size[u]){
swap(u,v);
swap(oldu, oldv);
}
side[v] = !(side[oldv]^side[oldu]);
size[u]+=size[v];
rep[v] = u;
}
};
int main() {
#ifndef ONLINE_JUDGE
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m,q; cin>>n>>m>>q;
vector<pair<int,int>> e;
for(int i = 0; i<m; i++){
int a,b; cin>>a>>b;
a--; b--;
e.emplace_back(a,b);
}
int result[200];
fill(result,result+200,-1);
for(int ii = 0; ii<200; ii++) {
dsu D(n);
for(int kk = 0; kk<min(ii,m); kk++) {
if(D.get(e[kk].first)!=D.get(e[kk].second))
D.merge(e[kk].first, e[kk].second);
else if(D.side[e[kk].first]==D.side[e[kk].second]){
result[ii] = INT_MAX;
goto fail;
}
}
for(int i = m-1; i>=ii; i--) {
int l = e[i].first, r = e[i].second;
if(D.get(l)!=D.get(r))
D.merge(l,r);
else if(D.side[l]==D.side[r]){
result[ii] = i;
break;
}
}
fail:
continue;
}
for(int j = 0; j<q; j++){
int l,b; cin>>l>>b;
l--;
if(b>result[l]) cout<<"NO\n";
else cout<<"YES\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
348 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
1 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
344 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Correct |
0 ms |
348 KB |
Output is correct |
| 26 |
Correct |
0 ms |
348 KB |
Output is correct |
| 27 |
Correct |
0 ms |
468 KB |
Output is correct |
| 28 |
Correct |
1 ms |
456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
348 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
1 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
344 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Correct |
0 ms |
348 KB |
Output is correct |
| 26 |
Correct |
0 ms |
348 KB |
Output is correct |
| 27 |
Correct |
0 ms |
468 KB |
Output is correct |
| 28 |
Correct |
1 ms |
456 KB |
Output is correct |
| 29 |
Runtime error |
4 ms |
604 KB |
Execution killed with signal 11 |
| 30 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
513 ms |
3896 KB |
Output is correct |
| 4 |
Correct |
1371 ms |
5084 KB |
Output is correct |
| 5 |
Correct |
352 ms |
5020 KB |
Output is correct |
| 6 |
Correct |
153 ms |
3796 KB |
Output is correct |
| 7 |
Correct |
157 ms |
3780 KB |
Output is correct |
| 8 |
Correct |
282 ms |
3528 KB |
Output is correct |
| 9 |
Correct |
337 ms |
4020 KB |
Output is correct |
| 10 |
Correct |
834 ms |
5004 KB |
Output is correct |
| 11 |
Correct |
569 ms |
3780 KB |
Output is correct |
| 12 |
Correct |
744 ms |
4884 KB |
Output is correct |
| 13 |
Correct |
263 ms |
2908 KB |
Output is correct |
| 14 |
Correct |
274 ms |
3464 KB |
Output is correct |
| 15 |
Correct |
672 ms |
4624 KB |
Output is correct |
| 16 |
Correct |
802 ms |
5132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
348 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
1 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
344 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Correct |
0 ms |
348 KB |
Output is correct |
| 26 |
Correct |
0 ms |
348 KB |
Output is correct |
| 27 |
Correct |
0 ms |
468 KB |
Output is correct |
| 28 |
Correct |
1 ms |
456 KB |
Output is correct |
| 29 |
Correct |
513 ms |
3896 KB |
Output is correct |
| 30 |
Correct |
1371 ms |
5084 KB |
Output is correct |
| 31 |
Correct |
352 ms |
5020 KB |
Output is correct |
| 32 |
Correct |
153 ms |
3796 KB |
Output is correct |
| 33 |
Correct |
157 ms |
3780 KB |
Output is correct |
| 34 |
Correct |
282 ms |
3528 KB |
Output is correct |
| 35 |
Correct |
337 ms |
4020 KB |
Output is correct |
| 36 |
Correct |
834 ms |
5004 KB |
Output is correct |
| 37 |
Correct |
569 ms |
3780 KB |
Output is correct |
| 38 |
Correct |
744 ms |
4884 KB |
Output is correct |
| 39 |
Correct |
263 ms |
2908 KB |
Output is correct |
| 40 |
Correct |
274 ms |
3464 KB |
Output is correct |
| 41 |
Correct |
672 ms |
4624 KB |
Output is correct |
| 42 |
Correct |
802 ms |
5132 KB |
Output is correct |
| 43 |
Correct |
495 ms |
8136 KB |
Output is correct |
| 44 |
Correct |
1448 ms |
7644 KB |
Output is correct |
| 45 |
Correct |
1228 ms |
7668 KB |
Output is correct |
| 46 |
Correct |
137 ms |
8112 KB |
Output is correct |
| 47 |
Correct |
141 ms |
8052 KB |
Output is correct |
| 48 |
Correct |
386 ms |
7876 KB |
Output is correct |
| 49 |
Correct |
830 ms |
7712 KB |
Output is correct |
| 50 |
Correct |
597 ms |
7876 KB |
Output is correct |
| 51 |
Correct |
727 ms |
7556 KB |
Output is correct |
| 52 |
Correct |
733 ms |
8032 KB |
Output is correct |
| 53 |
Correct |
221 ms |
6856 KB |
Output is correct |
| 54 |
Correct |
413 ms |
7880 KB |
Output is correct |
| 55 |
Correct |
674 ms |
7628 KB |
Output is correct |
| 56 |
Correct |
876 ms |
7652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
348 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
1 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
344 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Correct |
0 ms |
348 KB |
Output is correct |
| 26 |
Correct |
0 ms |
348 KB |
Output is correct |
| 27 |
Correct |
0 ms |
468 KB |
Output is correct |
| 28 |
Correct |
1 ms |
456 KB |
Output is correct |
| 29 |
Runtime error |
4 ms |
604 KB |
Execution killed with signal 11 |
| 30 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
348 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
1 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
344 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Correct |
0 ms |
348 KB |
Output is correct |
| 26 |
Correct |
0 ms |
348 KB |
Output is correct |
| 27 |
Correct |
0 ms |
468 KB |
Output is correct |
| 28 |
Correct |
1 ms |
456 KB |
Output is correct |
| 29 |
Runtime error |
4 ms |
604 KB |
Execution killed with signal 11 |
| 30 |
Halted |
0 ms |
0 KB |
- |
