Submission #1227210

#TimeUsernameProblemLanguageResultExecution timeMemory
1227210m5588ohammedJoker (BOI20_joker)C++20
25 / 100
414 ms24856 KiB
#include <bits/stdc++.h> using namespace std; #define endl "\n" #define mod 1000000009 #define int long long #define double long double int n,m,q; vector <array<int,2>> v[200001]; int disc[200001],odd=0,ans[200001]; set <int> qu; vector <array<int,2>> query; void solve(int i,int cnt,int l1,int r1){ disc[i]=cnt; for(auto [j,idx]:v[i]){ if(l1<=idx&&idx<=r1) continue; if(disc[j]!=0&&(disc[i]-disc[j])%2==0) odd++; if(disc[j]==0) solve(j,cnt+1,l1,r1); } return; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m>>q; for(int i=1;i<=m;i++){ int a,b; cin>>a>>b; v[a].push_back({b,i}); v[b].push_back({a,i}); } for(int i=1;i<=q;i++){ int l,r; cin>>l>>r; qu.insert(l); query.push_back({l,r}); } for(int bg:qu){ int l=bg,r=m; while(l<=r){ int mid=(l+r)/2; memset(disc,0,sizeof disc); odd=0; for(int i=1;i<=n;i++){ if(disc[i]==0) solve(i,1,bg,mid); } //cout<<mid<<" "<<odd<<endl; if(odd==0){ ans[bg]=mid; r=mid-1; } else l=mid+1; } } for(auto [l,r]:query){ if(ans[l]<=r) cout<<"NO"<<endl; else cout<<"YES"<<endl; } 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...