Submission #308238

#	Time	Username	Problem	Language	Result	Execution time	Memory
308238		VEGAnn	Joker (BOI20_joker)	C++14	100 / 100	285 ms	13540 KiB

Joker

#include <bits/stdc++.h>
#define i2 array<int,2>
#define i3 array<int,3>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
const int N = 200100;
const int M = 200100;
vector<i3> rollbacks;
int n, m, q, pre[N], siz[N], U[M], V[M], bnd[N], ht[N];
bool bad = 0;

i2 get(int x) {
    i2 res = {0, 0};

    while (x != pre[x]){
        res[1] ^= ht[x];
        x = pre[x];
    }

    res[0] = x;

    return res;
}

void link(int id){
    i2 x = get(U[id]), y = get(V[id]);

    if (x[0] == y[0]){
        if ((x[1] ^ y[1] ^ 1))
            bad = 1;
    } else {
        if (siz[x[0]] > siz[y[0]]) swap(x, y);

        // make new rollback

        rollbacks.PB({x[0], y[0], ht[x[0]]});

        siz[y[0]] += siz[x[0]];
        pre[x[0]] = y[0];
        ht[x[0]] ^= (x[1] ^ y[1] ^ 1);
    }
}

void calc(int l, int r, int cand_l, int cand_r){
    // cand_r < n

    int md = (l + r) >> 1;

    int mem = sz(rollbacks), res = 0;

    assert(!bad);

    for (int i = l; i < md; i++) {
        link(i);

        if (bad) {
            res = cand_r;
            break;
        }
    }

    for (int i = min(m - 1, cand_r); i >= max(cand_l, md); i--){
        if (bad) break;

        link(i);

        if (bad) {
            res = i;
            break;
        }
    }

    bnd[md] = res;
    bad = 0;

    while (sz(rollbacks) > mem){
        i3 cur = rollbacks.back(); rollbacks.pop_back();

        int x = cur[0], y = cur[1];

        ht[x] = cur[2];
        siz[y] -= siz[x];
        pre[x] = x;
    }

    if (l < md){
        for (int i = min(m - 1, cand_r); i > res; i--){
            link(i);

            if (bad) break;
        }

        if (bad){
            for (int i = l; i < md; i++)
                bnd[i] = res;
            bad = 0;
        } else calc(l, md - 1, cand_l, res);

        while (sz(rollbacks) > mem){
            i3 cur = rollbacks.back(); rollbacks.pop_back();

            int x = cur[0], y = cur[1];

            ht[x] = cur[2];
            siz[y] -= siz[x];
            pre[x] = x;
        }
    }

    if (r > md){
        for (int i = l; i < md + 1; i++){
            link(i);

            if (bad) break;
        }

        if (bad){
            for (int i = r; i > md; i--)
                bnd[i] = cand_r;
            bad = 0;
        } else calc(md + 1, r, max(md + 1, res), cand_r);

        while (sz(rollbacks) > mem){
            i3 cur = rollbacks.back(); rollbacks.pop_back();

            int x = cur[0], y = cur[1];

            ht[x] = cur[2];
            siz[y] -= siz[x];
            pre[x] = x;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m >> q;

    for (int i = 0; i < n; i++){
        pre[i] = i;
        siz[i] = 1;
        ht[i] = 0;
    }

    for (int i = 0; i < m; i++){
        cin >> U[i] >> V[i];
        U[i]--; V[i]--;
    }

    calc(0, m - 1, 0, m);

    for (int i = 0; i < q; i++){
        int l, r; cin >> l >> r; l--; r--;

        cout << (bnd[l] <= r ? "NO\n" : "YES\n");
    }

    return 0;
}

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