oj.uz

답안 #963998

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
963998 2024-04-16T07:32:24 Z owoovo Joker (BOI20_joker) C++17
0 / 100
 2000 ms 22364 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[400010],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+1);
    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--;
    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;
}

Compilation message

Joker.cpp: In member function 'void Dsu::init()':
Joker.cpp:14:41: warning: iteration 400010 invokes undefined behavior [-Waggressive-loop-optimizations]
   14 |         for(int i=0;i<=400050;i++)ori[i]=i,si[i]=1;
      |                                   ~~~~~~^~
Joker.cpp:14:22: note: within this loop
   14 |         for(int i=0;i<=400050;i++)ori[i]=i,si[i]=1;
      |                     ~^~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2016 ms 22364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2016 ms 22364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2016 ms 22364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2016 ms 22364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2016 ms 22364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2016 ms 22364 KB Time limit exceeded
2 Halted 0 ms 0 KB -