Submission #1095354

#TimeUsernameProblemLanguageResultExecution timeMemory
1095354duyhoanhoJoker (BOI20_joker)C++17
49 / 100
2058 ms32708 KiB
#include<bits/stdc++.h> #define int long long #define forinc(i,a,b) for(int i=a;i<=b;i++) #define fi first #define se second #define pii pair<int,int> #define pb push_back using namespace std; const int N = 2e5+10, S = 448; int n,m,q,p[N],sz[N],lz[N],x[N],y[N]; int ans[N]; bool ok; stack<pii> sk,pr,si,la; struct node { int l,r,id; } qu[N]; bool cmp(node a,node b) { if(a.l / S != b.l / S) return a.l < b.l; return a.r > b.r; } int pa(int v,int &c) { c ^= lz[v]; if(p[v] == v) return v; return pa(p[v],c); } void join(int a,int b) { int ca = 0; int cb = 0; a = pa(a,ca); b = pa(b,cb); if(sz[a] < sz[b]) swap(a,b); sk.push({a,b}); si.push({sz[a],sz[b]}); pr.push({p[a],p[b]}); la.push({lz[a],lz[b]}); if(a != b) { sz[a] += sz[b]; p[b] = a; if(ca == cb) lz[b] = 1; } } void rollback() { auto[a,b] = sk.top(); sk.pop(); auto[sza,szb] = si.top();si.pop(); sz[a] = sza; sz[b] = szb; auto[pa,pb] = pr.top(); pr.pop(); p[a] = pa ; p[b] = pb; auto[lza,lzb] = la.top(); la.pop(); lz[a] = lza ; lz[b] = lzb; } int get(int i) { return (i - 1) / S + 1; } bool check(int a,int b) { int ca = 0; int cb = 0; a = pa(a,ca); b = pa(b,cb); if(a == b && ca == cb) return true; return false; } int32_t main() { if(fopen("task.inp","r")) { freopen("task.inp","r",stdin); freopen("task.out","w",stdout); } ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>m>>q; for(int i=1; i<=m; i++) cin>>x[i]>>y[i]; forinc(i,1,q) { int l,r; cin>>l>>r; qu[i] = {l,r,i}; } sort(qu+1,qu+q+1,cmp); // forinc(i,1,q) cout<<qu[i].l<<" "<<qu[i].r<<" "<<qu[i].id<<"\n"; forinc(i,1,n) { sz[i] = 1; lz[i] = 0; p[i] = i; } for(int i=m; i>qu[1].r; i--) { if(check(x[i],y[i])) ok = 1; ans[qu[1].id] |= ok; join(x[i],y[i]); } for(int i=1; i<qu[1].l; i++) { if(check(x[i], y[i])) ans[qu[1].id] = 1; join(x[i],y[i]); } for(int t=2; t<=q; t++) { // auto[l,r,id] = qu[t]; if(get(qu[t].l) == get(qu[t-1].l)) { for(int i=1; i<qu[t-1].l; i++) rollback(); ans[qu[t].id] |= ok; for(int i=qu[t-1].r ; i > qu[t].r ; i--) { if(check(x[i],y[i])) ok = 1; ans[qu[t].id] |= ok; //cout<<t<<" "<<i<<" "<<x[i]<<" "<<y[i]<<" "<<check(x[i],y[i])<<" "<<qu[t].id<<"\n"; join(x[i],y[i]); } for(int i=1; i<qu[t].l; i++) { if(check(x[i],y[i])) ans[qu[t].id] = 1; join(x[i],y[i]); } } else { ok = 0; forinc(i,1,n) { sz[i] = 1; lz[i] = 0; p[i] = i; } while(sk.size()) { sk.pop(); la.pop(); si.pop(); pr.pop(); } for(int i=m; i>qu[t].r; i--) { if(check(x[i],y[i])) ok = 1; ans[qu[t].id] |= ok; join(x[i],y[i]); } for(int i=1; i<qu[t].l; i++) { if(check(x[i], y[i])) ans[qu[t].id] = 1; join(x[i],y[i]); } } } forinc(i,1,q) cout<<(ans[i] == 1 ? "YES\n" : "NO\n"); }

Compilation message (stderr)

Joker.cpp: In function 'int32_t main()':
Joker.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen("task.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen("task.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...