| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1043124 |
2024-08-04T00:42:31 Z |
wood |
Joker (BOI20_joker) |
C++17 |
|
1347 ms |
5052 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];
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>=0; 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 |
1 ms |
348 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 |
452 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 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 |
452 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
494 ms |
3780 KB |
Output is correct |
| 4 |
Correct |
1347 ms |
5052 KB |
Output is correct |
| 5 |
Correct |
331 ms |
4872 KB |
Output is correct |
| 6 |
Correct |
166 ms |
3776 KB |
Output is correct |
| 7 |
Correct |
156 ms |
3780 KB |
Output is correct |
| 8 |
Correct |
282 ms |
3524 KB |
Output is correct |
| 9 |
Correct |
331 ms |
4036 KB |
Output is correct |
| 10 |
Correct |
827 ms |
4984 KB |
Output is correct |
| 11 |
Correct |
538 ms |
3780 KB |
Output is correct |
| 12 |
Correct |
733 ms |
4840 KB |
Output is correct |
| 13 |
Correct |
238 ms |
2760 KB |
Output is correct |
| 14 |
Correct |
265 ms |
3352 KB |
Output is correct |
| 15 |
Correct |
648 ms |
4536 KB |
Output is correct |
| 16 |
Correct |
786 ms |
4984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 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 |
452 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 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 |
452 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 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 |
452 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
