Submission #1141416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141416		anmattroi	Joker (BOI20_joker)	C++17	0 / 100	117 ms	8700 KiB

Joker

/********************************************

Task: BalticOI20_Joker
Link: https://oj.uz/problem/view/BOI20_joker

********************************************/

#include <bits/stdc++.h>
#define maxn 200005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

constexpr int B = 100;

int n, m, q;
ii edge[maxn];

int rk[maxn];
ii par[maxn];
bool graph_is_bipartite = true;

int last[maxn];
bool nho[maxn];

vector<tuple<int, int, int, int, int> > Stack;

void rollback() {
    assert(!Stack.empty());
    auto [u, rku, v, rkv, state] = Stack.back(); Stack.pop_back();
    par[u] = {u, 0};
    par[v] = {v, 0};
    rk[u] = rku;
    rk[v] = rkv;
    graph_is_bipartite = state;
}

ii find_set(int v) {
    if (v == par[v].fi) return ii{v, 0};
    ii tr = find_set(par[v].fi);
    return ii{tr.fi, tr.se^par[v].se};
}


bool union_set(int u, int v) {
    ii tu = find_set(u), tv = find_set(v);
    int a = tu.fi, b = tv.fi;
    if (tu.fi == tv.fi) {
        if (tu.se == tv.se) {
            Stack.emplace_back(a, rk[a], b, rk[b], graph_is_bipartite);
            graph_is_bipartite = false;
            return true;
        }
        return false;
    }

    if (rk[a] > rk[b]) swap(a, b);
    Stack.emplace_back(a, rk[a], b, rk[b], graph_is_bipartite);
    par[a] = {b, tu.se^tv.se^1};
    rk[b] += rk[a] == rk[b];
    return true;
}



void solve(int l1 = 1, int l2 = m, int r1 = 1, int r2 = m) {
    int mid = (l1 + l2) / 2;
    for (int i = l1; i <= mid; i++) nho[i] = union_set(edge[i].fi, edge[i].se);
    for (int i = r2; i >= r1; i--) {
        nho[i] = union_set(edge[i].fi, edge[i].se);
        if (!graph_is_bipartite) {
            last[mid] = i+1;
            break;
        }
    }
    assert(last[mid]);
    for (int i = last[mid]-1; i <= r2; i++) if (nho[i]) rollback();
    for (int i = mid; i >= l1; i--) if (nho[i]) rollback();

    for (int i = last[mid]+1; i <= r2; i++) nho[i] = union_set(edge[i].fi, edge[i].se);
    if (l1 < mid) solve(l1, mid-1, r1, last[mid]);

    for (int i = last[mid]+1; i <= r2; i++) if (nho[i]) rollback();


    for (int i = l1; i <= mid; i++) nho[i] = union_set(edge[i].fi, edge[i].se);
    if (mid < l2) solve(mid+1, l2, last[mid], r2);
    for (int i = l1; i <= mid; i++) if (nho[i]) rollback();

}

void sub0() {
    for (int i = 1; i <= m; i++) union_set(edge[i].fi, edge[i].se);
    if (graph_is_bipartite) {
        while (q--) {
            int l, r;
            cin >> l >> r;
            cout << "NO\n";
        }
        exit(0);
    }
    while (!Stack.empty()) rollback();
}

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

    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) cin >> edge[i].fi >> edge[i].se;
    for (int i = 1; i <= n; i++) par[i] = {i, 0};

    sub0();

    int p = m;
    union_set(edge[m].fi, edge[m].se);
    for (int i = 1; i <= m; i++) {
        union_set(edge[i].fi, edge[i].se);
        if (!graph_is_bipartite) {
            p = i-1;
            break;
        }
    }

    for (int i = p+1; i <= m; i++) last[i] = m+1;
    while (!Stack.empty()) rollback();

    solve(1, p, 1, m);
    while (!Stack.empty()) rollback();

    last[0] = m+1;
    for (int i = m; i >= 1; i--) {
        union_set(edge[i].fi, edge[i].se);
        if (!graph_is_bipartite) {
            last[0] = i+1;
            break;
        }
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << (r+1 >= last[l-1] ? "NO\n" : "YES\n");
    }

}
/*
6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
4 8
4 7
*/

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