oj.uz

Submission #899240

# Submission time Handle Problem Language Result Execution time Memory
899240 2024-01-05T16:07:58 Z Darren0724 Joker (BOI20_joker) C++17
25 / 100
 450 ms 35520 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);
    int p=m;
    while(st.size()){
        undo();
    }
    while(p>0){
        p--;
        if(onion(p)){
            break;
        }
    }
    for(int i=0;i<q;i++){
        int a,b;cin>>a>>b;a--;b--;
        if(a==0){
            cout<<(b<p?"YES":"NO")<<endl;
            continue;
        }
        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 4 ms 14428 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct
4 Incorrect 5 ms 14424 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 351 ms 23056 KB Output is correct
4 Correct 450 ms 33984 KB Output is correct
5 Correct 358 ms 33848 KB Output is correct
6 Correct 288 ms 27332 KB Output is correct
7 Correct 330 ms 25980 KB Output is correct
8 Correct 309 ms 22736 KB Output is correct
9 Correct 324 ms 26696 KB Output is correct
10 Correct 327 ms 34756 KB Output is correct
11 Correct 308 ms 26056 KB Output is correct
12 Correct 335 ms 34748 KB Output is correct
13 Correct 282 ms 20172 KB Output is correct
14 Correct 325 ms 22980 KB Output is correct
15 Correct 298 ms 26836 KB Output is correct
16 Correct 322 ms 35520 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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