Submission #1276534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276534		jioung	Joker (BOI20_joker)	C++20	0 / 100	147 ms	13824 KiB

Joker

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

#define io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define eb emplace_back
#define endl '\n'

typedef long long ll;
typedef pair<int, int> pii;

const int INF = 1e9;
const int MOD = 998244353;
const int MAXN = 4e5 + 5;
const int MAXM = 2e5 + 5;
int lab[MAXN];
int n, m, q;
pii ed[MAXM];
vector<tuple<int, int, int, int, bool>> history;
void Init() {
    for (int i = 1; i <= 2 * n; i++) lab[i] = -1;
    history.clear();
}
int Find (int u) {
    if (lab[u] < 0) return u;
    return Find(lab[u]);
}
int snapshot () {
    return (int)history.size();
}
bool biparte = false;
void Union (int u, int v) {
    int ru = Find(u), rv = Find(v);
    if (ru != rv) {
        if (lab[ru] > lab[rv]) swap(ru, rv);
        history.eb(ru, lab[ru], rv, lab[rv], biparte);
        lab[ru] += lab[rv];
        lab[rv] = ru;
        if (Find(u) == Find(u + n)) biparte = true;
//        if (Find(v) == Find(v + n)) biparte = true;
    }
}
void rollback(int snap) {
    while (history.size() > snap) {
        auto [ru, lru, rv, lrv, bip] = history.back();
        history.pop_back();
        lab[ru] = lru;
        lab[rv] = lrv;
        biparte = bip;
    }
}
int ans[MAXM];

void calc (int L, int R, int optL, int optR) {
    if (L > R) return;
    int mid = (L + R) >> 1;
    int snap = snapshot();
    for (int i = L; i < mid; i++) {
        Union(ed[i].fi, ed[i].se + n);
        Union(ed[i].se, ed[i].fi + n);
    }

    if (biparte == true) {
        for (int i = mid; i <= R; i++) ans[i] = m + 1;
        rollback(snap);
        calc(L, mid - 1, optL, optR);
        return;
    }
    ans[mid] = optL;
    for (int i = optR; i >= max(mid, optL); i--) {
        Union(ed[i].fi, ed[i].se + n);
        Union(ed[i].se, ed[i].fi + n);
        if (biparte == true) {
            ans[mid] = i;
            break;
        }
    }

    rollback(snap);
    int snap2 = snapshot();
    for (int i = L; i <= mid; i++) {
        Union(ed[i].fi, ed[i].se + n);
        Union(ed[i].se, ed[i].fi + n);
    }
    calc(mid + 1, R, ans[mid], optR);
    rollback(snap2);
    int snap3 = snapshot();
    for (int i = optR; i >= max(mid, optL); i--) {
        Union(ed[i].fi, ed[i].se + n);
        Union(ed[i].se, ed[i].fi + n);
    }
    calc(L, mid - 1, optL, ans[mid]);
    rollback(snap3);
}

void solve() {
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)  {
        cin >> ed[i].fi >> ed[i].se;
    }
    Init();
    calc(1, m, 1, m);
    while (q --) {
        int l, r; cin >> l >> r;
        if(ans[l] > r) cout << "YES\n";
        else cout << "NO\n";
    }
}

int main() {
    io;
    solve();
    return 0;
}

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