Submission #964016

#	Time	Username	Problem	Language	Result	Execution time	Memory
964016		owoovo	Joker (BOI20_joker)	C++17	100 / 100	251 ms	65732 KiB

Joker

#include<bits/stdc++.h>
#pragma GCC opitimize("O3,unroll-loops")
#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;
    inline void init(){
        for(int i=0;i<=400050;i++)ori[i]=i,si[i]=1;
        while(!move.empty())move.pop();
    }
    inline int f(int a){
        return ori[a]==a?a:f(ori[a]);
    }
    inline 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;
    }
    inline void undo(){
        auto [p,id]=move.top();
        auto [a,b]=p;
        ori[a]=a;
        si[b]-=si[a];
        move.pop();
        return;
    }
}dsu;
inline 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;
}
inline 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;
}
inline 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--){
            if(l+1<=U)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;
}

Compilation message (stderr)

Joker.cpp:2: warning: ignoring '#pragma GCC opitimize' [-Wunknown-pragmas]
    2 | #pragma GCC opitimize("O3,unroll-loops")
      |

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 22 / 22
• Subtask 6: 29 / 29