Submission #1244842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244842		nguyn	Joker (BOI20_joker)	C++20	100 / 100	322 ms	21284 KiB

Joker

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

const int N = 2e5 + 5;

struct DSU {
    int n;
    vector<int> par;
    vector<int> sz;
    vector<int> d;
    int ok;

    vector<pair<int&, int>> his;

    DSU () {}
    DSU (int n) : n(n) {
        ok = 1;
        d.assign(n + 1, 0);
        par.resize(n + 1);
        sz.assign(n + 1, 1);
        for (int i = 1; i <= n; i++) par[i] = i;
    }

    pii find(int x) {
        if (par[x] == x) {
            return {x, 0};
        }
        pii tmp = find(par[x]);
        return {tmp.F, tmp.S ^ d[x]};
    }

    void join(int x, int y) {
        pii u = find(x);
        pii v = find(y);
        if (u.F == v.F) {
            if (u.S == v.S) {
                his.pb({ok, ok});
                ok = 0;
            }
            return;
        }
        if (sz[u.F] < sz[v.F]) swap(u, v);
        his.pb({sz[u.F], sz[u.F]});
        his.pb({par[v.F], par[v.F]});
        his.pb({d[v.F], d[v.F]});
        his.pb({ok, ok});

        sz[u.F] += sz[v.F];
        par[v.F] = u.F;
        d[v.F] = v.S ^ u.S ^ 1;
    }

    int snapshot() {
        return his.size();
    }

    void rollback(int until) {
        while(his.size() > until) {
            his.back().F = his.back().S;
            his.pop_back();
        }
    }
} dsu;

int n, m, q;
pii edges[N];
int f[N];

void cal(int l, int r, int optl, int optr) {
    if (l > r) return;
    int mid = (l + r) / 2;
    int checker = dsu.snapshot();
    for (int i = l; i < mid; i++) {
        dsu.join(edges[i].F, edges[i].S);
    }
    int best = optr;
    bool sta = 0;
    for (int i = optr; i >= max(optl, mid); i--) {
        if (dsu.ok) {
            best = i;
            sta = 1;
        }
        else {
            break;
        }
        dsu.join(edges[i].F, edges[i].S);
    }
    if (sta) f[mid] = best;
    else f[mid] = m + 1;
    dsu.rollback(checker);
    for (int i = optr; i > best; i--) {
        dsu.join(edges[i].F, edges[i].S);
    }
    cal(l, mid - 1, optl, best);
    dsu.rollback(checker);
    for (int i = l; i < mid + 1; i++) {
        dsu.join(edges[i].F, edges[i].S);
    }
    cal(mid + 1, r, best, optr);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        edges[i] = {u, v};
    }
    dsu = DSU(n);
    cal(1, m, 1, m);
//    for (int i = 1; i <= m; i++) {
//        cout << i << ' ' << f[i] << '\n';
//    }
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        if (r < f[l]) {
            cout << "YES\n";
        }
        else {
            cout << "NO\n";
        }
    }
}

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