oj.uz

Submission #964012

# Submission time Handle Problem Language Result Execution time Memory
964012 2024-04-16T07:48:33 Z owoovo Joker (BOI20_joker) C++17
25 / 100
 2000 ms 53280 KB 
#include<bits/stdc++.h>
#define ll long long
#define F first 
#define S second
using namespace std;
vector<pair<int,int>> node[800010];
vector<pair<int,int>> edge;
int cnt,R,U;
int ans[200010];
struct Dsu{
    int ori[400100],si[400100];
    stack<pair<pair<int,int>,int>> move;
    void init(){
        for(int i=0;i<=400050;i++)ori[i]=i,si[i]=1;
        while(!move.empty())move.pop();
    }
    int f(int a){
        return ori[a]==a?a:f(ori[a]);
    }
    bool onion(int a,int b,int id){
        a=f(a),b=f(b);
        if(a==b)return false;
        if(si[a]>si[b])swap(a,b);
        ori[a]=b;
        si[b]+=si[a];
        move.push({{a,b},id});
        return true;
    }
    void undo(){
        auto [p,id]=move.top();
        auto [a,b]=p;
        ori[a]=a;
        si[b]-=si[a];
        move.pop();
        return;
    }
}dsu;
bool addedge(int u,int v,int id){
    if(dsu.onion(u*2,v*2+1,id)^dsu.onion(u*2+1,v*2,id))return false;
    else return true;
}
void add(int l,int r,int nl,int nr,int id,int u,int v){
    if(l==nl&&r==nr){
        node[id].push_back({u,v});
        return ;
    }
    int m=(nl+nr)>>1;
    if(r<=m){
        add(l,r,nl,m,id*2+1,u,v);
    }else if(m<l){
        add(l,r,m+1,nr,id*2+2,u,v);
    }else{
        add(l,m,nl,m,id*2+1,u,v);
        add(m+1,r,m+1,nr,id*2+2,u,v);
    }
    return;
}
void vis(int l,int r,int id){
    for(auto x:node[id]){
        addedge(x.F,x.S,id);
    }
    if(l==r){
        int gogo=R,L=U-l;
        while(gogo>L){
            if(addedge(edge[gogo].F,edge[gogo].S,id)==false){
                break;
            }else{
                gogo--;
            }
        }
        gogo++;
        ans[U-l]=gogo;
        for(int i=R;i>=gogo;i--){
            add(l+1,U,0,U,0,edge[i].F,edge[i].S);
        }
        R=gogo-1;
        while(!dsu.move.empty()&&dsu.move.top().S==id)dsu.undo();
        return;
    }
    int m=(l+r)>>1;
    vis(l,m,id*2+1);
    vis(m+1,r,id*2+2);
    while(!dsu.move.empty()&&dsu.move.top().S==id)dsu.undo();
    return;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n,m,q;
    cin>>n>>m>>q;
    U=1;
    R=m;
    dsu.init();
    edge.push_back({0,0});
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        edge.push_back({u,v});
    }
    while(U<=m){
        if(addedge(edge[U].F,edge[U].S,0)==false){
            break;
        }else{
            U++;
        }
    }
    U--;
    if(U==m){
        for(int i=0;i<q;i++){
            cout<<"NO\n";
        }
        return 0;
    }
    dsu.init();
    for(int i=1;i<=U;i++){
        add(0,U-i,0,U,0,edge[i].F,edge[i].S);
    }
    for(int i=U+1;i<=m;i++)ans[i]=m+5;
    vis(0,U,0);
    // for(int i=0;i<=m;i++){
    //     cout<<ans[i]<<" ";
    // }
    // cout<<"\n";
    for(int i=0;i<q;i++){
        int l,r;
        cin>>l>>r;
        l--;
        r++;
        if(r>=ans[l]){
            cout<<"NO\n";
        }else{
            cout<<"YES\n";
        }
    }
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22364 KB Output is correct
2 Correct 11 ms 22284 KB Output is correct
3 Correct 11 ms 22364 KB Output is correct
4 Execution timed out 2094 ms 22364 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22364 KB Output is correct
2 Correct 11 ms 22284 KB Output is correct
3 Correct 11 ms 22364 KB Output is correct
4 Execution timed out 2094 ms 22364 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22364 KB Output is correct
2 Correct 11 ms 22284 KB Output is correct
3 Correct 171 ms 51516 KB Output is correct
4 Correct 50 ms 31984 KB Output is correct
5 Correct 191 ms 53280 KB Output is correct
6 Correct 133 ms 44852 KB Output is correct
7 Correct 139 ms 44532 KB Output is correct
8 Correct 157 ms 45360 KB Output is correct
9 Correct 162 ms 46280 KB Output is correct
10 Correct 197 ms 50032 KB Output is correct
11 Correct 154 ms 48080 KB Output is correct
12 Correct 220 ms 48900 KB Output is correct
13 Correct 145 ms 45256 KB Output is correct
14 Correct 168 ms 45968 KB Output is correct
15 Correct 183 ms 48624 KB Output is correct
16 Correct 193 ms 50372 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22364 KB Output is correct
2 Correct 11 ms 22284 KB Output is correct
3 Correct 11 ms 22364 KB Output is correct
4 Execution timed out 2094 ms 22364 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22364 KB Output is correct
2 Correct 11 ms 22284 KB Output is correct
3 Correct 11 ms 22364 KB Output is correct
4 Execution timed out 2094 ms 22364 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22364 KB Output is correct
2 Correct 11 ms 22284 KB Output is correct
3 Correct 11 ms 22364 KB Output is correct
4 Execution timed out 2094 ms 22364 KB Time limit exceeded
5 Halted 0 ms 0 KB -