Submission #1227281

#TimeUsernameProblemLanguageResultExecution timeMemory
1227281AlmontherJoker (BOI20_joker)C++20
0 / 100
2096 ms32340 KiB
#include<bits/stdc++.h> #define ll long long #define co cout<< using namespace std; // stuff const int maxn=2e5+5; ll n,m,q; vector<pair<ll,ll>>edges; vector<pair<ll,ll>>qu[maxn]; vector<ll>v[maxn],v1[maxn]; ll ans[maxn]; ll c[maxn],bad=0,bad1=0,c1[maxn]; void dfs(ll x){ if(bad||bad1) return; ll red=0,blue=0; for(auto i:v[x]){ if(c[i]==1) red=1; if(c[i]==2) blue=1; } if((red==1&&blue==1)||(red==1&&c[x]==1)||(blue==1&&c[x]==2)){ bad=1; return; } if(blue) c[x]=1; else c[x]=2; for(auto i:v[x]) if(c[i]==0) dfs(i); v[x].clear(); red=0,blue=0; for(auto i:v1[x]){ if(c1[i]==1) red=1; else if(c1[i]==2) blue=1; } if((red==1&&blue==1)||(red==1&&c1[x]==1)||(blue==1&&c1[x]==2)){ bad1=1; return; } if(blue) c1[x]=1; else c1[x]=2; for(auto i:v1[x]) if(c1[i]==0) dfs(i); v1[x].clear(); } void solve(){ cin>>n>>m>>q; for(int i=0;i<m;i++){ ll a,b; cin>>a>>b; edges.push_back({a,b}); } for(int i=0;i<q;i++){ ll l,r; cin>>l>>r; qu[r].push_back({l+1,i}); } for(int i=0;i<=m;i++) sort(qu[i].begin(),qu[i].end()); for(int i=m;i>=0;i--){ if(i<m){ v[edges[i].first].push_back(edges[i].second); v[edges[i].second].push_back(edges[i].first); dfs(edges[i].first); } if(qu[i].size()==0) continue; ll pt=0; for(int i=1;i<=n;i++) c1[i]=c[i],bad1=bad; for(int j=0;j<=i;j++){ if(j){ v1[edges[j].first].push_back(edges[j].second); v1[edges[j].second].push_back(edges[j].first); dfs(edges[j].first); } while(pt<qu[i].size()&&qu[i][pt].first==j) ans[qu[i][pt].second]=bad|bad1,pt++; if(qu[i].size()==pt) break; } } for(int i=0;i<q;i++) co ((ans[i])?"YES\n":"NO\n"); } int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int _=1; // cin>>_; while(_--) solve(); }
#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...