제출 #551827

#제출 시각아이디문제언어결과실행 시간메모리
551827oleh1421Joker (BOI20_joker)C++17
25 / 100
530 ms21296 KiB
//#pragma GCC target("avx2") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> //#define endl '\n' using namespace __gnu_pbds; typedef long double ld; //#define int ll using namespace std; mt19937 rnd(time(NULL)); typedef long long ll; const int N=400100; const int K=10000; int a[N],b[N]; int ans[N]; int l[N/K+1]; int r[N/K+1]; int group[N]; int w[N]; int sz[N]; int dsu[N]; bool BAD=false; vector<pair<int,pair<int,int> > >CH; pair<int,int>get(int x){ if (x==dsu[x]) return {x,w[x]}; auto cur=get(dsu[x]); cur.second^=w[x]; return cur; } void unite(int a,int b){ if (a==0 && b==0) return; auto x=get(a); auto y=get(b); if (x.first==y.first){ if (x.second==y.second){ CH.push_back({4,{-1,BAD}}); BAD=true; } return; } if (sz[x.first]>sz[y.first]) swap(x,y); CH.push_back({1,{x.first,dsu[x.first]}}); CH.push_back({2,{y.first,sz[y.first]}}); CH.push_back({3,{x.first,w[x.first]}}); dsu[x.first]=y.first; sz[y.first]+=sz[x.first]; w[x.first]^=(x.second^y.second^1^w[y.first]); } void roll_back(){ if (!CH.empty()){ auto cur=CH.back(); CH.pop_back(); if (cur.first==1) dsu[cur.second.first]=cur.second.second; else if (cur.first==2) sz[cur.second.first]=cur.second.second; else if (cur.first==3) w[cur.second.first]=cur.second.second; else BAD=cur.second.second; } } int L[N],R[N]; bool used[N]; int n,m,q; void rec(int l,int r,int L,int R){ if (l>r) return; int m=(l+r)/2; int len=CH.size(); for (int i=l;i<=m;i++){ unite(a[i],b[i]); } int ind=-1; for (int i=R;i>=L;i--){ unite(a[i],b[i]); if (BAD){ ind=i; break; } } ans[m]=ind; while (CH.size()>len) roll_back(); for (int i=R;i>ind;i--){ unite(a[i],b[i]); } rec(l,m-1,L,ind); while (CH.size()>len) roll_back(); for (int i=R;i>ind;i--){ unite(a[i],b[i]); } for (int i=l;i<=m;i++){ unite(a[i],b[i]); } rec(m+1,r,ind,R); } void solve(){ cin>>n>>m>>q; for (int i=1;i<=m;i++){ cin>>a[i]>>b[i]; } for (int i=1;i<=q;i++){ cin>>L[i]>>R[i]; used[L[i]-1]=true; } for (int i=1;i<=n;i++){ dsu[i]=i; sz[i]=1; w[i]=0; } BAD=false; for (int i=1;i<=m;i++){ unite(a[i],b[i]); } if (!BAD){ for (int i=0;i<=m;i++) ans[i]=0; } else { while (!CH.empty()) roll_back(); rec(0,m,1,m+1); } for (int i=1;i<=q;i++){ if (ans[L[i]-1]<=R[i]) cout<<"NO\n"; else cout<<"YES\n"; } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int tt=1; while (tt--){ solve(); } return 0; } /** 6 8 2 1 3 1 5 1 6 2 5 2 6 3 4 3 5 5 6 4 8 4 7 **/

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

Joker.cpp: In function 'void rec(int, int, int, int)':
Joker.cpp:79:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |     while (CH.size()>len) roll_back();
      |            ~~~~~~~~~^~~~
Joker.cpp:84:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |     while (CH.size()>len) roll_back();
      |            ~~~~~~~~~^~~~
#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...