Submission #1054523

#TimeUsernameProblemLanguageResultExecution timeMemory
1054523allin27xJoker (BOI20_joker)C++17
49 / 100
2055 ms12856 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]; int e1[2*N]; void build1(int N) {for (int i=0; i<N; i++) e1[i] = -1;} int get1(int x) { return e1[x] < 0 ? x : e1[x] = get1(e1[x]); } bool conn1(int a, int b) { return get1(a) == get1(b); } int size1(int x) { return -e1[get1(x)]; } void unite1(int x, int y) { x = get1(x), y = get1(y); if (x == y) return; if (e1[x] > e1[y]) swap(x, y); e1[x] += e1[y]; e1[y] = x; } int nd = 0; int ch[2*N]; int e2[2*N]; void build2(int N) {for (int i=0; i<N; i++) e2[i] = -1;} int get2(int x) { if (e2[x] < 0) return x; ch[nd++] = x; return e2[x] = get2(e2[x]); } bool conn2(int a, int b) { return get2(a) == get2(b); } int size2(int x) { return -e2[get2(x)]; } void unite2(int x, int y) { x = get2(x), y = get2(y); if (x == y) return; if (e2[x] > e2[y]) swap(x, y); ch[nd++] = x; ch[nd++] = y; e2[x] += e2[y]; e2[y] = x; } int st[2*N]; 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()); build1(2*n); build2(2*n); int fM =0; for (int t=0; t<SQRT; t++){ for (int i=0; i<2*n; i++) e2[i] = e1[i],st[i] = e2[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; nd = 0; for (int ll=t*SQRT; ll<p.l; ll++){ if (conn2(edges[ll][0],edges[ll][1])) f++; unite2(edges[ll][0]+n, edges[ll][1]); unite2(edges[ll][0], edges[ll][1]+n); } for (int rr =0; rr<nd; rr++){ e2[ch[rr]] = st[ch[rr]]; } if (f || fm || fM) ans[p.i] = 1; j--; if (j<0) break; p = queries[t][j]; } if (j<0) break; nd = 0; fm += conn2(edges[i][0], edges[i][1]); unite2(edges[i][0] + n, edges[i][1]); unite2(edges[i][0], edges[i][1] + n); for (int rr =0; rr<nd; rr++){ st[ch[rr]] = e2[ch[rr]]; } i--; } for (int ll=SQRT*t; ll<min(m, SQRT*t + SQRT); ll++){ fM += conn1(edges[ll][0], edges[ll][1]); unite1(edges[ll][0] + n, edges[ll][1]); unite1(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...