oj.uz

Submission #901932

# Submission time Handle Problem Language Result Execution time Memory
901932 2024-01-10T04:27:31 Z 089487 Joker (BOI20_joker) C++14
0 / 100
 442 ms 19012 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse4,abm,avx,popcnt")
#include<bits/stdc++.h>
//#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define F first
#define S second
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef pair<int,int> pii;
void debug(){
    cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
    cout<<a<<" ",debug(b...);
}
const int N=5e5+2;
const int INF=1e18;
pii e[N];
int p[N];
int sz[N];
void init(int n){
    rep(i,1,n) p[i]=i,sz[i]=1;
}
int fp(int x){
    if(x!=p[x]) return fp(p[x]);
    return x;
}
int ans[N];
stack<tuple<int,int,int>> state;
int n,m;
int neg(int x){
    return x>n?x-n:x+n;
}
void _Union(int a,int b){
    a=fp(a);
    b=fp(b);
    if(sz[a]<sz[b]) swap(a,b);
    state.push(make_tuple(a,sz[a],b));
    p[b]=a;
    sz[a]+=sz[b];
    return ;
}
bool Union(int a,int b){
    int fa=fp(a);
    int fb=fp(b);
    if(a==b) return false;
    _Union(fa,b+n);
    _Union(fb,a+n);
    return true;
}
void undo(){
    auto [a,sza,b]=state.top();
    state.pop();
    sz[a]=sza;
    p[b]=b;
}
void solve(int l,int r,int vl,int vr){
    if(l>r) return ;
    //debug("solve",l,r,vl,vr);
    if(vl==vr){
        rep(i,l,r) ans[i]=vl;
        return ;
    }
    int mid=(l+r)>>1;
    ans[mid]=vr;
    int T0=sz(state);
    if(r<=vl){
        int t0=sz(state);
        for(int i=mid;i<=r;i++){
            Union(e[i].F,e[i].S);
        }
        int t1=sz(state)-(r==vl)*2;
        for(int i=max(r+1,vl);i<=vr;i++){
            if(!Union(e[i].F,e[i].S)){
                ans[mid]=i-1;
                break;
            }
        }
        while(sz(state)>t1) undo();
        solve(l,mid-1,vl,ans[mid]);
        while(sz(state)>t0) undo();
        for(int i=vl;i<ans[mid];i++) Union(e[i].F,e[i].S);
        solve(mid+1,r,ans[mid],vr);
    }
    else{
        int t0=sz(state);
        for(int i=mid;i<=vr;i++){
            if(!Union(e[i].F,e[i].S)) {
                ans[mid]=i-1;
                break;
            }
        }
        //debug("mid",mid,"ans",ans[mid]);
        repd(t,ans[mid],max(vl,mid)){
            undo();undo();
        }
        solve(l,mid-1,vl,ans[mid]);
        while(sz(state)>t0) undo();
        rep(t,r+1,ans[mid]-1){
            Union(e[t].F,e[t].S);
        }
        solve(mid+1,r,ans[mid],vr);
    }
    while(sz(state)>T0) undo();
}
signed main(){
	quick
    int q;
    cin>>n>>m>>q;
    init(n*2);
    rep(i,0,m-1){
        cin>>e[i].F>>e[i].S;
        e[i+m]=e[i];
    }
    int m0=m;
    m*=2;
    solve(0,m-1,0,m-1);
    /*rep(i,0,m-1){
        cout<<ans[i]<<" \n"[i==m-1];
    }*/
    /*rep(i,0,m-1){
        init(2*n);
        ans[i]=-1;
        rep(j,i,m-1){
            if(Union(e[j].F,e[j].S)) ans[i]=j;
            else break;
        }
        cout<<ans[i]<<" \n"[i==m-1];
    }*/
    string Ans[2]={"YES","NO"};
    while(q--){
        int l,r;
        cin>>l>>r;
        --l,--r;
        cout<<Ans[(ans[r+1]>=l+m0-1)]<<"\n";
    }
}

Compilation message

Joker.cpp:25:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   25 | const int INF=1e18;
      |               ^~~~
Joker.cpp: In function 'void undo()':
Joker.cpp:60:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     auto [a,sza,b]=state.top();
      |          ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 442 ms 19012 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -