oj.uz

Submission #905318

# Submission time Handle Problem Language Result Execution time Memory
905318 2024-01-13T01:40:05 Z Darren0724 Joker (BOI20_joker) C++17
0 / 100
 132 ms 26716 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7512 KB Output is correct
2 Correct 3 ms 7512 KB Output is correct
3 Correct 4 ms 7668 KB Output is correct
4 Correct 4 ms 7516 KB Output is correct
5 Correct 4 ms 7516 KB Output is correct
6 Runtime error 10 ms 14808 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7512 KB Output is correct
2 Correct 3 ms 7512 KB Output is correct
3 Correct 4 ms 7668 KB Output is correct
4 Correct 4 ms 7516 KB Output is correct
5 Correct 4 ms 7516 KB Output is correct
6 Runtime error 10 ms 14808 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7512 KB Output is correct
2 Correct 3 ms 7512 KB Output is correct
3 Runtime error 132 ms 26716 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7512 KB Output is correct
2 Correct 3 ms 7512 KB Output is correct
3 Correct 4 ms 7668 KB Output is correct
4 Correct 4 ms 7516 KB Output is correct
5 Correct 4 ms 7516 KB Output is correct
6 Runtime error 10 ms 14808 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7512 KB Output is correct
2 Correct 3 ms 7512 KB Output is correct
3 Correct 4 ms 7668 KB Output is correct
4 Correct 4 ms 7516 KB Output is correct
5 Correct 4 ms 7516 KB Output is correct
6 Runtime error 10 ms 14808 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7512 KB Output is correct
2 Correct 3 ms 7512 KB Output is correct
3 Correct 4 ms 7668 KB Output is correct
4 Correct 4 ms 7516 KB Output is correct
5 Correct 4 ms 7516 KB Output is correct
6 Runtime error 10 ms 14808 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -