oj.uz

Submission #1039437

# Submission time Handle Problem Language Result Execution time Memory
1039437 2024-07-30T21:33:51 Z MarwenElarbi Joker (BOI20_joker) C++17
25 / 100
 654 ms 27432 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 = m; 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 3 ms 7256 KB Output is correct
2 Correct 2 ms 7092 KB Output is correct
3 Correct 2 ms 7260 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 3 ms 7256 KB Output is correct
2 Correct 2 ms 7092 KB Output is correct
3 Correct 2 ms 7260 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 3 ms 7256 KB Output is correct
2 Correct 2 ms 7092 KB Output is correct
3 Correct 516 ms 17660 KB Output is correct
4 Correct 622 ms 27432 KB Output is correct
5 Correct 450 ms 25572 KB Output is correct
6 Correct 464 ms 22468 KB Output is correct
7 Correct 482 ms 22392 KB Output is correct
8 Correct 485 ms 20880 KB Output is correct
9 Correct 577 ms 21952 KB Output is correct
10 Correct 654 ms 25088 KB Output is correct
11 Correct 561 ms 22464 KB Output is correct
12 Correct 583 ms 25212 KB Output is correct
13 Correct 540 ms 20468 KB Output is correct
14 Correct 537 ms 21440 KB Output is correct
15 Correct 582 ms 23748 KB Output is correct
16 Correct 634 ms 25600 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7256 KB Output is correct
2 Correct 2 ms 7092 KB Output is correct
3 Correct 2 ms 7260 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 3 ms 7256 KB Output is correct
2 Correct 2 ms 7092 KB Output is correct
3 Correct 2 ms 7260 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 3 ms 7256 KB Output is correct
2 Correct 2 ms 7092 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Incorrect 2 ms 7260 KB Output isn't correct
5 Halted 0 ms 0 KB -