oj.uz

Submission #1039438

# Submission time Handle Problem Language Result Execution time Memory
1039438 2024-07-30T21:35:22 Z MarwenElarbi Joker (BOI20_joker) C++17
25 / 100
 682 ms 27936 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define se second
#define fi first
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
const int nax = 2e5 + 5;
vector<int> adj[nax];
vector<pair<int,int>> edges(nax);
int opt[nax];
struct DSU{
    vector<pair<int,int>> parent;
    vector<vector<int>> hist;
    vector<int> rank;
    bool bip=true;
    void init(int n){
        parent.resize(n);
        rank.assign(n,0);
        for (int i = 0; i < n; ++i)
        {
            parent[i]={i,0};
        }
        return;
    }
    bool is_bip(){
        return bip;
    }
    pair<int,int> find(int x){
        if(x!=parent[x].fi){
            int len=parent[x].se;
            pair<int,int> v=find(parent[x].fi);
            v.se=(v.se+len)%2;
            return v;
        }
        return parent[x];
    }
    void join(int x,int y){
        if(x==y)
            return;
        pair<int,int> xx=find(x);
        pair<int,int> yy=find(y);
        if(xx.fi==yy.fi){
            hist.pb({-1,bip});
            if(xx.se==yy.se){
                bip=0;
            }
            return;
        }
        if(rank[xx.fi]<rank[yy.fi]) swap(xx,yy);
        hist.pb({yy.fi,parent[yy.fi].fi,parent[yy.fi].se,xx.fi,(rank[xx.fi]==rank[yy.fi])});
        parent[yy.fi].fi=xx.fi;
        parent[yy.fi].se=(yy.se+xx.se+1)%2;
        rank[xx.fi]+=(rank[xx.fi]==rank[yy.fi]);
    }
    void roll_back(){
        auto last=hist.back();
        hist.pop_back();
        if(last[0]==-1){
            bip=last.back();
        }else{
            parent[last[0]]={last[1],last[2]};
            rank[last[3]]-=last[4];
        }
    }
    void roll_back(int x){
        while(x--){
            roll_back();
        }
    }
}dsu;
int n,m,q;
void daq(int l,int r,int optl,int optr){
    if(l>r) return;
    int mid=(r+l)/2;
    int cnt=0;
    for (int i = l; i < mid; ++i)
    {
        cnt++;
        dsu.join(edges[i].fi,edges[i].se);
    }
    int optimum=optr;
    for (int i = optr; i >= max(mid,optl) ; --i)
    {
        if(!dsu.is_bip()){
            break;
        }
        optimum=i;
        if(i<m){
            cnt++;
            dsu.join(edges[i].fi,edges[i].se);
        }
    }
    opt[mid]=optimum;
    dsu.roll_back(cnt);
    cnt=0;
    for (int i = optimum; i <= optr; ++i)
    {
        if(i==m) continue;
        cnt++;
        dsu.join(edges[i].fi,edges[i].se);
    }
    daq(l,mid-1,optl,optimum);
    dsu.roll_back(cnt);
    cnt=0;
    for (int i = mid; i <= mid; ++i)
    {
        cnt++;
        dsu.join(edges[i].fi,edges[i].se);
    }
    daq(mid+1,r,optimum,optr);
    dsu.roll_back(cnt);
    cnt=0;
}
int main(){
    cin>>n>>m>>q;
    dsu.init(n);
    for (int i = 0; i < m; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        edges[i]={x,y};
        adj[x].pb(y);
        adj[y].pb(x);
    }
    daq(0,m-1,0,m);
    for (int i = 0; i < q; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        cout << (opt[x] > y ? "YES" : "NO")<<endl;
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7092 KB Output is correct
4 Incorrect 2 ms 7260 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7092 KB Output is correct
4 Incorrect 2 ms 7260 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 532 ms 17776 KB Output is correct
4 Correct 632 ms 27936 KB Output is correct
5 Correct 481 ms 21372 KB Output is correct
6 Correct 501 ms 18376 KB Output is correct
7 Correct 494 ms 18500 KB Output is correct
8 Correct 484 ms 17652 KB Output is correct
9 Correct 533 ms 18668 KB Output is correct
10 Correct 682 ms 21764 KB Output is correct
11 Correct 600 ms 18372 KB Output is correct
12 Correct 556 ms 21112 KB Output is correct
13 Correct 574 ms 16320 KB Output is correct
14 Correct 553 ms 17552 KB Output is correct
15 Correct 606 ms 19732 KB Output is correct
16 Correct 638 ms 21920 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7092 KB Output is correct
4 Incorrect 2 ms 7260 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7092 KB Output is correct
4 Incorrect 2 ms 7260 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7092 KB Output is correct
4 Incorrect 2 ms 7260 KB Output isn't correct
5 Halted 0 ms 0 KB -