oj.uz

답안 #964015

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
964015 2024-04-16T07:50:31 Z owoovo Joker (BOI20_joker) C++17
25 / 100
 2000 ms 53300 KB 
#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--){
            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

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

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 22328 KB Output is correct
2 Correct 12 ms 22360 KB Output is correct
3 Correct 16 ms 22176 KB Output is correct
4 Execution timed out 2077 ms 22364 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 22328 KB Output is correct
2 Correct 12 ms 22360 KB Output is correct
3 Correct 16 ms 22176 KB Output is correct
4 Execution timed out 2077 ms 22364 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 22328 KB Output is correct
2 Correct 12 ms 22360 KB Output is correct
3 Correct 177 ms 51488 KB Output is correct
4 Correct 58 ms 31972 KB Output is correct
5 Correct 178 ms 53300 KB Output is correct
6 Correct 127 ms 44860 KB Output is correct
7 Correct 151 ms 44484 KB Output is correct
8 Correct 161 ms 45432 KB Output is correct
9 Correct 179 ms 46276 KB Output is correct
10 Correct 183 ms 49864 KB Output is correct
11 Correct 159 ms 48068 KB Output is correct
12 Correct 182 ms 49036 KB Output is correct
13 Correct 144 ms 45544 KB Output is correct
14 Correct 162 ms 45776 KB Output is correct
15 Correct 201 ms 48576 KB Output is correct
16 Correct 205 ms 50472 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 22328 KB Output is correct
2 Correct 12 ms 22360 KB Output is correct
3 Correct 16 ms 22176 KB Output is correct
4 Execution timed out 2077 ms 22364 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 22328 KB Output is correct
2 Correct 12 ms 22360 KB Output is correct
3 Correct 16 ms 22176 KB Output is correct
4 Execution timed out 2077 ms 22364 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 22328 KB Output is correct
2 Correct 12 ms 22360 KB Output is correct
3 Correct 16 ms 22176 KB Output is correct
4 Execution timed out 2077 ms 22364 KB Time limit exceeded
5 Halted 0 ms 0 KB -