Submission #1175916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175916		Pekiban	Joker (BOI20_joker)	C++20	100 / 100	270 ms	20896 KiB

Joker

#include <bits/stdc++.h>

using namespace std;
#define pb push_back

const int N = 2e5 + 5;
array<int, 2> e[N];
struct DSU {
    vector<pair<int &, int>> H;
    int p[N], sz[N], cl[N], ok;
    void init(int n) {
        iota(p, p+n+1, 0);
        fill(sz, sz+n+1, 1);
        fill(cl, cl+n+1, 0);
        ok = 1;
    }
    int get(int u) {
        if (u == p[u])  return u;
        return get(p[u]);
    }
    int dep(int u) {
        if (u == p[u])  return 0;
        return cl[u] ^ dep(p[u]);
    }
    bool unite(int u, int v) {
        int d1 = dep(u), d2 = dep(v);
        u = get(u), v = get(v);
        if (u == v) {
            if (d1 == d2) {
                H.pb({ok, ok});
                ok = 0;
            }
            return 0;
        }
        if (sz[u] < sz[v])  swap(u, v);
        H.pb({sz[u], sz[u]});
        H.pb({p[v], p[v]});
        H.pb({cl[v], cl[v]});
        sz[u] += sz[v], p[v] = u, cl[v] = (d1 + d2 + 1) & 1;
        return 1;
    }
    void rollback(int x) {
        while (H.size() > x) {
            H.back().first = H.back().second;
            H.pop_back();
        }
    }
} D;
int f[N];
void dq(int l, int r, int tl, int tr) {
    if (r < l)  return;
    int m = (l+r)/2;
    int z = D.H.size();
    for (int i = r; i > m; --i) D.unite(e[i][0], e[i][1]);
    int j = tl;
    while (j <= m && D.ok) {
        D.unite(e[j][0], e[j][1]);
        ++j;
    }
    f[m] = j;
    D.rollback(z);
    for (int i = r; i >= m; --i) D.unite(e[i][0], e[i][1]);
    dq(l, m-1, tl, j);
    D.rollback(z);
    for (int i = tl; i < j; ++i)    D.unite(e[i][0], e[i][1]);
    dq(m+1, r, j, tr);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= m; ++i)    cin >> e[i][0] >> e[i][1];
    D.init(n);
    dq(1, m, 1, m);
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << (l >= f[r] ? "YES" : "NO") << '\n';
    }
}
// f[i] = minimalno j tako da graf bez ivica j,j+1,...,i nije bipartitivan.

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