Submission #973151

#	Time	Username	Problem	Language	Result	Execution time	Memory
973151		the_coding_pooh	Joker (BOI20_joker)	C++14	100 / 100	986 ms	25160 KiB

Joker

#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

#define fs first
#define sc second

const int SIZE = 2e5 + 5;

const int PERSIST = -1, IS_BIPARTITE = -2;

struct check_bipartite{
    int N, pl ;

    struct Disjoint_Set_Union{
        stack <pair<int, int>> rollback;

        int DSU[2 * SIZE];

        bool status = 1;

        inline void init(int n){
            for (int i = 0; i <= 2 * n;i++){
                DSU[i] = -1;
            }
            return;
        }

        inline int find_parent(int node){
            if(DSU[node] < 0)
                return node;

            int pa = find_parent(DSU[node]);
            rollback.push({node, DSU[node]});
    
            return DSU[node] = pa;
        }

        inline void merge(int a, int b){
            a = find_parent(a);
            b = find_parent(b);
    
            if(a == b)
                return;
    
            rollback.push({a, DSU[a]});
            rollback.push({b, DSU[b]});

            if(DSU[b] <= DSU[a])
                swap(a, b);

            DSU[a] += DSU[b];
            DSU[b] = a;
            return;
        }

        inline void checkpoint(){
            rollback.push({PERSIST, 0});
            return;
        }

        inline void roll(){
            while(rollback.top().fs != PERSIST){
                if(rollback.top().fs == IS_BIPARTITE)
                    status = rollback.top().sc;
                else{
                    DSU[rollback.top().fs] = rollback.top().sc;
                }
                rollback.pop();
            }
            rollback.pop();
            return;
        }
    } dsu;

    void add(int a, int b){
        dsu.merge(a, b + N), dsu.merge(b, a + N);
        if(dsu.find_parent(a) == dsu.find_parent(a + N) || dsu.find_parent(b) == dsu.find_parent(b + N)){
            dsu.rollback.push({IS_BIPARTITE, dsu.status});
            dsu.status = 0;
        }
    }
}black_box;

int lft[SIZE];

pair <int, int> edge[SIZE];

void solve(int nl, int nr, int pl, int pr){
    // cout << nl << ' ' << nr << ' ' << pl << ' ' << pr << '\n';
    int nm = (nl + nr) / 2, pm;
    
    black_box.dsu.checkpoint();
    
    for (int i = nr; i > nm; i--){
        black_box.add(edge[i].fs, edge[i].sc);
    }
    
    black_box.dsu.checkpoint();
    
    pm = pl - 1;
    
    while(black_box.dsu.status && pm <= min(nm, pr - 1)){
        pm++;
        black_box.add(edge[pm].fs, edge[pm].sc);
    }
    
    black_box.dsu.roll();
    
    lft[nm] = pm;
    black_box.add(edge[nm].fs, edge[nm].sc);

    // cout << nm << ' ' << pm << '\n';

    if(pm > 0 && nl != nm)
        solve(nl, nm - 1, pl, pm);
    
    black_box.dsu.roll(), black_box.dsu.checkpoint();

    for (int i = pl; i < pm; i++){
        black_box.add(edge[i].fs, edge[i].sc);
    }
    
    if(nm != nr)
        solve(nm + 1, nr, max(pm, 1), pr);
    
    black_box.dsu.roll();
    return;
}

int main(){
    int N, M, Q;
    
    cin >> N >> M >> Q;
    
    black_box.N = N;
    black_box.dsu.init(N);
    
    for (int i = 1; i <= M;i++){
        cin >> edge[i].fs >> edge[i].sc;
    }

    solve(1, M, 1, M + 1);
    /*
    for (int i = 1; i <= M;i++){
        cout << i << ' ' << lft[i] << '\n';
    }
    */
    for (int l, r; Q--;){
        cin >> l >> r;
        lft[r] < l ? cout << "YES\n" : cout << "NO\n";
    }
}

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