Submission #899228

#	Time	Username	Problem	Language	Result	Execution time	Memory
899228		Darren0724	Joker (BOI20_joker)	C++17	0 / 100	375 ms	27412 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
const int N=200005;
const int M=500005;
const int INF=1e9;
const int mod=1e9+7;
vector<int> e1(N<<1),e2(N<<1);
vector<int> pa(N<<1),sz(N<<1,1);
vector<int> dp(N);
vector<tuple<int,int,int,int>> st;
int Find(int k){
    if(pa[k]==k){
        return k;
    }
    return pa[k]=Find(pa[k]);
}
void onion2(int a,int b){
    a=Find(a);
    b=Find(b);
    if(a==b){
        return;
    }
    if(sz[a]>sz[b]){
        swap(a,b);
    }
    st.push_back({a,pa[a],b,sz[b]});
    pa[a]=b;
    sz[b]+=sz[a];
}
int onion1(int a,int b){
    onion2(a,b+N);
    onion2(a+N,b);
    return Find(a)==Find(a+N);
}
int onion(int i){
    return onion1(e1[i],e2[i]);
}
void undo(){
    auto [a,b,c,d]=st.back();
    st.pop_back();
    pa[a]=b;
    sz[c]=d;
}
void dc(int a,int b,int l,int r){
    if(a>=b){
        return;
    }
    if(r==l){
        for(int i=a;i<b;i++){
            dp[i]=l;
        }
        return;
    }
    //cout<<a<<' '<<b<<' '<<l<<' '<<r<<endl;
    int c=(a+b)>>1;
    int flag=0;
    int rec1=st.size();
    for(int i=a;i<c;i++){
        flag|=onion(i);
    }
    if(flag){
        for(int j=c;j<b;j++){
            dp[j]=r;
        }
    }
    int rec=st.size();
    for(int j=r-1;j>=l;j--){
        if(onion(j)){
            dp[c]=j+1;
            undo();
            break;
        }
        if(j==l)dp[j]=l;
    }
    //cout<<"dp "<<c<<' '<<dp[c]<<endl;
    
    while(st.size()>rec){
        undo();
    }
    if(!flag)dc(c+1,b,dp[c],r);
    while(st.size()>rec1){
        undo();
    }
    for(int i=r-1;i>=dp[c];i--){
        onion(i);
    }
    dc(a,c,l,dp[c]);
}
int32_t main() {
    LCBorz;
    iota(all(pa),0);
    int n,m,q;cin>>n>>m>>q;
    for(int i=0;i<m;i++){
        cin>>e1[i]>>e2[i];
    }
    dc(0,m+1,0,m);
    for(int i=0;i<q;i++){
        int a,b;cin>>a>>b;a--;b--;
        cout<<(b>=dp[a-1]?"YES":"NO")<<endl;
    }
    
    return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'void dc(long long int, long long int, long long int, long long int)':
Joker.cpp:80:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::tuple<long long int, long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   80 |     while(st.size()>rec){
      |           ~~~~~~~~~^~~~
Joker.cpp:84:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::tuple<long long int, long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   84 |     while(st.size()>rec1){
      |           ~~~~~~~~~^~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29