oj.uz

Submission #899228

# Submission time Handle Problem Language Result Execution time Memory
899228 2024-01-05T15:56:17 Z Darren0724 Joker (BOI20_joker) C++17
0 / 100
 375 ms 27412 KB 
#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

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.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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