Submission #1054343

#TimeUsernameProblemLanguageResultExecution timeMemory
1054343allin27xJoker (BOI20_joker)C++17
25 / 100
221 ms262144 KiB
#include <bits/stdc++.h> using namespace std; 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> e; DSU(int N) { e = vector<int>(N, -1); } int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } bool conn(int a, int b) { return get(a) == get(b); } int size(int x) { return -e[get(x)]; } void unite(int x, int y) { x = get(x), y = get(y); if (x == y) return; if (e[x] > e[y]) swap(x, y); e[x] += e[y]; e[y] = x; } }; 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[l/SQRT].push_back(p); } for (int i=0; i<SQRT; i++) sort(queries[i].begin(), queries[i].end()); DSU dsu1(2*n); DSU dsu2(2*n); DSU dsu3(2*n); int fM =0; for (int t=0; t<SQRT; t++){ for (int i=0; i<2*n; i++) dsu2.e[i] = dsu1.e[i]; for (int i=0; i<2*n; i++) dsu3.e[i] = dsu1.e[i]; if (t*SQRT >= m) break; int fm = 0; int i = m-1; int j = queries[t].size()-1; while (i>=0){ if (j<0) break; qr p = queries[t][j]; while (p.r == i){ int f = 0; for (int ll=t*SQRT; ll<p.l; ll++){ if (dsu3.conn(edges[ll][0],edges[ll][1])) f++; dsu3.unite(edges[ll][0]+n, edges[ll][1]); dsu3.unite(edges[ll][0], edges[ll][1]+n); } for (int ll=t*SQRT; ll<p.l; ll++){ int a = edges[ll][0]; int b = edges[ll][1]; int c = a+n; int d = b+n; dsu3.e[a] = dsu2.e[a]; dsu3.e[b] = dsu2.e[b]; dsu3.e[c] = dsu2.e[c]; dsu3.e[d] = dsu2.e[d]; } if (f || fm || fM) ans[p.i] = 1; j--; if (j<0) break; p = queries[t][j]; } if (j<0) break; fm += dsu3.conn(edges[i][0], edges[i][1]); dsu2.unite(edges[i][0] + n, edges[i][1]); dsu2.unite(edges[i][0], edges[i][1] + n); dsu3.unite(edges[i][0] + n, edges[i][1]); dsu3.unite(edges[i][0], edges[i][1] + n); i--; } for (int ll=SQRT*t; ll<min(m, SQRT*t + SQRT); ll++){ fM += dsu1.conn(edges[ll][0], edges[ll][1]); dsu1.unite(edges[ll][0] + n, edges[ll][1]); dsu1.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...