Submission #1043126

#TimeUsernameProblemLanguageResultExecution timeMemory
1043126woodJoker (BOI20_joker)C++17
41 / 100
1448 ms8136 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...