Submission #905318

#	Time	Username	Problem	Language	Result	Execution time	Memory
905318		Darren0724	Joker (BOI20_joker)	C++17	0 / 100	132 ms	26716 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
#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;
vector<int> st1;
int valid=0;
int n,m,q;
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);
    while(st.size()>st1.size()){
        st1.push_back(valid);
    }
    valid|=(Find(a)==Find(a+N));
    return valid;
}
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;
    valid=st1.back();
    st1.pop_back();
}
// | 1 2 3 4 | 5 6 7 8 
void dc(int l,int r,int a,int b){
    if(r<l)return;
    b=min(m,b);
    //cout<<l<<' '<<r<<' '<<a<<' '<<b<<endl;
    int mi=(l+r)>>1;
    int rec1=st.size();
    for(int i=l;i<mi;i++){
        onion(i);
    }
    int rec=st.size();
    if(valid){
        //cout<<mi<<endl;
        dp[mi]=b+1;
    }
    else{
        int last=b;
        for(int i=b;i>=a;i--){
            if(onion(i)){
                break;
            }
            last--;
        }
        dp[mi]=last;
    }
    while(st.size()>rec){
        undo();
    }
    onion(mi);
    dc(mi+1,r,dp[mi],b);
    while(st.size()>rec1){
        undo();
    }
    for(int i=b;i>dp[mi];i--){
        onion(i);
    }
    dc(l,mi-1,a,dp[mi]);
    while(st.size()>rec1){
        undo();
    }
}
int32_t main() {
    LCBorz;
    iota(all(pa),0);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        cin>>e1[i]>>e2[i];
    }
    dc(1,m,1,m);
    for(int i=1;i<m;i++){
        assert(dp[i]<=dp[i+1]);
    }
    for(int i=0;i<q;i++){
        int a,b;cin>>a>>b;
        if(b>=dp[a]){
            cout<<"NO"<<endl;
        }
        else{
            cout<<"YES"<<endl;
        }
    }
    
    return 0;
}
/*
3 15 10
1 2
2 3
3 1
1 2
2 3
3 1
1 2
2 3
3 1
1 2
2 3
3 1
1 2
2 3
3 1
*/

Compilation message (stderr)

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