Submission #1185262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185262		patgra	Joker (BOI20_joker)	C++20	0 / 100	0 ms	320 KiB

Joker

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

int n, m, q;
vector<pair<int, int>> edges, queries;
vector<int> bestAns;
vector<int> rep, depth, rel;
bool isOk;
vector<array<int, 6>> changes; // curTime  v  rep  dep  rel  isok
int curTime;

pair<int, int> fuFind(int x) { 
    if(rep[x] == x) return {x, 0};
    auto [a, b] = fuFind(rep[x]);
    b ^= rel[x];
    return {a, b};
}

void fuUnion(int x, int y, int rl) {
    auto [xx, xr] = fuFind(x);
    auto [yy, yr] = fuFind(y);
    if(xx == yy) {
        if((rl ^ xr ^ yr) && !isOk) {
            isOk = true;
            changes.pb({curTime, 0, rep[0], depth[0], rel[0], 0});
        }
        curTime++;
        return;
    }
    x = xx, y = yy;
    changes.pb({curTime, x, rep[x], depth[x], rel[x], isOk});
    changes.pb({curTime, y, rep[y], depth[y], rel[y], isOk});
    if(depth[x] < depth[y]) {
        rep[x] = rep[y];
        depth[y] = max(depth[y], depth[x] + 1);
        rel[x] = xr ^ yr ^ rl;
    }
    else { 
        rep[y] = x;
        depth[x] = max(depth[x], depth[y] + 1);
        rel[y] = xr ^ yr ^ rl;
    }
    curTime++;
}

void undoTime() {
    curTime--;
    while(!changes.empty() && changes.back()[0] >= curTime) {
        auto [_, v, rp, dp, rl, io] = changes.back();
        rep[v] = rp;
        depth[v] = dp;
        rel[v] = rl;
        isOk = io;
        changes.pop_back();
    }
}

void dq(int larg, int rarg, int lval, int rval) {
    if(larg > rarg) return;
    int marg = (larg + rarg) / 2;
    rep(i, larg, marg + 1) fuUnion(edges[i].first, edges[i].second, 1);
    auto ogRval = rval;
    while(!isOk && rval > max(lval, marg)) {
        auto [x, y] = edges[rval--];
        fuUnion(x, y, 1);
    }
    bestAns[marg] = rval;
    auto finalRval = rval;
    while(rval < ogRval) undoTime(), rval++;
    dq(marg + 1, rarg, finalRval, rval);
    rep(i, larg, marg + 1) undoTime();
    while(rval > finalRval) {
        auto [x, y] = edges[rval--];
        fuUnion(x, y, 1);
    }
    dq(larg, marg - 1, lval, finalRval);
    while(rval < ogRval) undoTime(), rval++;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> m >> q;
    edges.resize(m);
    queries.resize(q);
    bestAns.resize(m);
    rep.resize(n), depth.resize(n), rel.resize(n);
    rep(i, 0, n) rep[i] = i;
    int x, y;
    rep(i, 0, m) cin >> x >> y, edges[i] = {x-1, y-1};
    dq(0, m - 1, 0, m - 1);
    rep(i, 0, m) DC << bestAns[i] << ' ';
    DC << eol;
    rep(i, 0, q) cin >> x >> y, cout << (bestAns[max(x - 2, 0)] >= y - 1 ? "YES" : "NO") << '\n';
}

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