제출 #930598

#제출 시각아이디문제언어결과실행 시간메모리
930598Faisal_SaqibJoker (BOI20_joker)C++17
0 / 100
101 ms31676 KiB
#include <bits/stdc++.h> using namespace std; const int M=2e5+1; int n,m,q; bool mark[M],vis[M],cycle=0; int val[M],par[M],h[M]; vector<int> com[M]; vector<pair<int,int>> ma[M],query,edges; int mx_r_for_l[M]; bool found=0; void dfs(int x) { vis[x]=1; for(auto [y,ind]:ma[x]) { if(mark[ind]) continue; if(!vis[y]) { val[y]=(val[x]+1)%2; dfs(y); } else if((val[y]+1)%2!=val[x]) { found=1; } } } bool check(int l,int r) { // cout<<"Check "<<l<<' '<<r<<endl; for(int i=1;i<=n;i++) vis[i]=0; for(int i=0;i<m;i++) mark[i]=(l<=i and i<=r); found=0; for(int i=1;i<=n;i++) { if(!vis[i]) { dfs(i); } } // cout<<"Answer "<<found<<endl; return found; } void init(){ cycle=0; for(int i=1;i<=n;i++) { h[i]=0; par[i]=i; com[i]={i}; } } void add_edge(int ind) { int u=edges[ind].first; int v=edges[ind].second; int pu=par[u]; int pv=par[v]; // cout<<"Hola "<<u<<' '<<v<<endl; // cout<<pu<<' '<<pv<<endl; if(pu==pv) { if(h[u]==h[v]) { cycle=1; } } else{ int cp=(h[u]!=h[v]); u=pu; v=pv; if(com[u].size()>com[v].size()) swap(u,v); for(auto ver:com[u]) { com[v].push_back(ver); par[ver]=v; h[ver]=(h[ver]+cp)%2; } com[u].clear(); } } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin>>n>>m>>q; for(int i=0;i<m;i++) { int a,b; cin>>a>>b; // cout<<i+1<<"th edge is "<<a<<' '<<b<<endl; ma[a].push_back({b,i}); ma[b].push_back({a,i}); edges.push_back({a,b}); } vector<int> difl={-1}; for(int lp=0;lp<q;lp++) { int l,r; cin>>l>>r; l--; r--; query.push_back({l,r}); difl.push_back(l); } sort(begin(difl),end(difl)); for(int i=1;i<difl.size();i++) { if(difl[i-1]!=difl[i]) { int l=difl[i]; int r=m; init(); for(int p=0;p<l;p++) add_edge(p); while(!cycle) { r--; add_edge(r); } mx_r_for_l[l]=r-1; } } for(auto [l,r]:query) { if(mx_r_for_l[l]>=r) { // cout<<"Query "<<l<<' '<<r<<endl; cout<<"YES"<<'\n'; } else{ cout<<"NO"<<'\n'; } } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Joker.cpp: In function 'int main()':
Joker.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for(int i=1;i<difl.size();i++)
      |                 ~^~~~~~~~~~~~
#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...