Submission #446932

#	Time	Username	Problem	Language	Result	Execution time	Memory
446932		Ozy	Joker (BOI20_joker)	C++17	0 / 100	2067 ms	10108 KiB

Joker

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 200000
#define val first
#define x second

lli n,m,q,c,d;
lli res[MAX+2],from[MAX+2],to[MAX+2],xr[MAX+2],padres[MAX+2],tam[MAX+2];
lli bip;
stack<pair<lli,lli> > histo;

pair<lli,lli> Find(lli a) {
    if (padres[a] == a) return {a, xr[a]};
    pair<lli,lli> nuevo = Find(padres[a]);
    nuevo.x ^= xr[a];
    return nuevo;
}

void Undo() {
    pair<lli,lli> a = histo.top();
    histo.pop();

    if (a.first == -1) {
        bip = a.second;
        return;
    }
    padres[a.second] = a.second;
    tam[a.first] -= tam[a.second];
    xr[a.second] = 0;
}

void Union(lli a, lli b) {
    pair<lli,lli> A = Find(a);
    pair<lli,lli> B = Find(b);

    if (A.val == B.val) {
        histo.push({-1,bip});
        if (A.x == B.x) bip = 0;
        return;
    }

    if (tam[A.val] < tam[B.val]) swap(A,B);
    xr[B.val] = 1ll ^ A.x ^ B.x;
    padres[B.val] = A.val;
    tam[A.val] += tam[B.val];
    histo.push({A.val, B.val});
}

void DC(lli ini, lli fin, lli l, lli r) {

    if (ini > fin) return;
    lli sum = 0;
    lli op;
    lli mitad = (ini+fin)/2;

    res[mitad] = m+1;
    rep (i,ini,mitad-1) Union(from[i],to[i]),sum++;
    repa(i,r,max(mitad,l)) Union(from[i],to[i]), sum++;

    if (bip) res[mitad] = max(mitad,l) - 1;
    else {
        rep(i,max(mitad,l),r) {
            Undo();
            sum--;
            if (bip) {
                res[mitad] = i;
                while (sum) {Undo(); sum--;}
                break;
            }
        }
    }

    while (sum) {Undo(); sum--;}
    op = min(res[mitad],m);

    rep(i,ini,mitad) {Union(from[i], to[i]); sum++;}
    DC(mitad+1,fin,l,op);
    while (sum) {Undo(); sum--;}

    rep(i,op+1,r) {Union(from[i], to[i]); sum++;}
    DC(ini,mitad-1,l,op);
    while (sum) {Undo(); sum--;}
}

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

    cin >> n >> m >> q;
    rep(i,1,m) cin >> from[i] >> to[i];

    bip = 1;
    rep(i,1,n) {padres[i] = i; tam[i] = 1;}
    DC(1,m,1,m);

    rep(i,1,q) {
        cin >> c >> d;
        if (res[c] < d) cout << "NO\n";
        else cout << "YES\n";
    }
    return 0;
}

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