Submission #1054270

#TimeUsernameProblemLanguageResultExecution timeMemory
1054270allin27xJoker (BOI20_joker)C++17
0 / 100
1732 ms20508 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int mod = 1e9+7; #define forn(i,n) for(int i=0; i<n; i++) #define readv(a,n) vector<int>a(n);forn(i,n)cin>>a[i]; #define readvv(a,n,m) vector<vector<int>> a(n,vector<int>(m));forn(i,n)forn(j,m)cin>>a[i][j]; #define all(a) a.begin(), a.end() #define _max(x,y) x = max(x,y) #define _min(x,y) x = min(x,y) // #define f first // #define s second const int N = 2e5+4; const int SQRT = 460; int ans[N]; struct qr{ int l, r, i; bool operator<(qr b){ return make_pair(l/SQRT, -r) < make_pair(b.l/SQRT,-b.r); } }; vector<qr> queries[SQRT]; int edges[N][2]; struct DSU{ vector<int> par; vector<int> size; stack<int> rb; int cmp; DSU(int n){ par.resize(n); for(int i=0; i<n; ++i) par[i]=i; size.resize(n,1); cmp = n; } int get(int p){ return par[p]==p? p: get(par[p]); } void unite(int a, int b){ a = get(a); b = get(b); if (a==b){ rb.push(-1); return; } cmp--; if (size[a] > size[b]) swap(a,b); rb.push(a); size[b]+=size[a]; par[a] = b; } int conn(int a, int b){ return get(a) == get(b); } void rollback(){ int f = rb.top(); rb.pop(); if (f==-1) return; cmp++; size[par[f]] -= size[f]; par[f] = f; } }; void solve(){ int n,m,q; cin>>n>>m>>q; for (int i=0; i<m; i++){ int a,b; cin>>a>>b; a--;b--; edges[i][0]=a; edges[i][1] = b; } for (int i=0; i<q; i++){ int l,r; cin>>l>>r; l--; r--; qr p; p.l=l;p.r=r;p.i=i; queries[i/SQRT].push_back(p); } for (int i=0; i<SQRT; i++) sort(queries[i].begin(), queries[i].end()); DSU dsu(2*n); int fM =0; for (int t=0; t<SQRT; t++){ int fm = 0; int i = m-1; int j = queries[t].size()-1; while (i>=0 && j>=0){ qr p = queries[t][j]; while (p.r == i){ int f = 0; for (int ll=t*SQRT; ll<=p.l; ll++){ if (dsu.conn(edges[ll][0],edges[ll][1])) f++; dsu.unite(edges[ll][0]+n, edges[ll][1]); dsu.unite(edges[ll][0], edges[ll][1]+n); } for (int ll=t*SQRT; ll<=p.l; ll++){ dsu.rollback(); dsu.rollback(); } if (f || fm || fM) ans[p.i] = 1; j--; if (j<0) break; p = queries[t][j]; } fm += dsu.conn(edges[i][0], edges[i][1]); dsu.unite(edges[i][0] + n, edges[i][1]); dsu.unite(edges[i][0], edges[i][1] + n); i--; } for (int ll=2*(i+1); ll<2*m; ll++) dsu.rollback(); for (int ll=SQRT*t; ll<min(m, SQRT*t + SQRT); ll++){ fM += dsu.conn(edges[ll][0], edges[ll][1]); dsu.unite(edges[ll][0] + n, edges[ll][1]); dsu.unite(edges[ll][0], edges[ll][1] + n); } } for (int i=0;i<q; i++) cout<<(ans[i]?"YES\n":"NO\n"); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; while(t--){ solve(); } 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...