# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1043121 | 2024-08-04T00:39:05 Z | wood | Joker (BOI20_joker) | C++17 | 1 ms | 348 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 freopen("/home/ioi/CLionProjects/ioi/input.txt ","r",stdin); #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); } 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; } } } 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; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |