Submission #963731

#	Time	Username	Problem	Language	Result	Execution time	Memory
963731		Pring	Joker (BOI20_joker)	C++17	100 / 100	276 ms	18088 KiB

Joker

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

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

const int MXN = 200005;
int n, m, q, x, y;
int eu[MXN], ev[MXN];
int l[MXN], L;

struct DSU {
    int p[MXN * 2];
    vector<pii> st;
    vector<bool> isb;
    void init(int n) {
        fill(p + 1, p + n * 2 + 1, -1);
        st.clear();
        isb.clear();
        isb.push_back(0);
    }
    int find(int x) {
        return (p[x] < 0 ? x : find(p[x]));
    }
    bool onion(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            st.push_back(mp(0, 0));
            st.push_back(mp(0, 0));
            return false;
        }
        if (p[x] > p[y]) swap(x, y);
        st.push_back(mp(x, p[x]));
        st.push_back(mp(y, p[y]));
        p[x] += p[y];
        p[y] = x;
        return true;
    }
    void undo() {
        p[st.back().fs] = st.back().sc;
        st.pop_back();
        p[st.back().fs] = st.back().sc;
        st.pop_back();
    }
    bool ONION(int x, int y) {
        onion(x, y + n);
        onion(x + n, y);
        bool f = (isb.back() | (find(x) == find(y)));
        isb.push_back(f);
        return f;
    }
    void BACK() {
        undo();
        undo();
        isb.pop_back();
    }
} dsu;

int ODD_CYCLE() {
    dsu.init(n);
    FOR(i, 0, m) if (dsu.ONION(eu[i], ev[i])) return i + 1;
    return -1;
}

void MOVE() {
    while (!dsu.isb.back()) {
        dsu.ONION(eu[L], ev[L]);
        L++;
    }
}

void MOVE(int x) {
    while (L < x) {
        dsu.ONION(eu[L], ev[L]);
        L++;
    }
    while (L > x) {
        dsu.BACK();
        L--;
    }
}

void calc(int sl, int sr) {
    if (sl == sr) return;
    int mid = (sl + sr) >> 1;
    for (int i = sr; i > mid; i--) dsu.ONION(eu[i - 1], ev[i - 1]);
    int pl = L;
    MOVE();
    l[mid] = L;
    MOVE(pl);
    calc(sl, mid);
    for (int i = sr; i > mid; i--) dsu.BACK();
    MOVE(l[mid]);
    calc(mid + 1, sr);
    MOVE(pl);
}

void miku() {
    cin >> n >> m >> q;
    FOR(i, 0, m) cin >> eu[i] >> ev[i];
    l[m] = ODD_CYCLE();
    if (l[m] == -1) {
        while (q--) cout << "NO" << '\n';
        return;
    }
    dsu.init(n);
    calc(0, m);
    // FOR(i, 0, m + 1) cout << l[i] << '\n';
    while (q--) {
        cin >> x >> y;
        cout << (x > l[y] ? "YES" : "NO") << '\n';
    }
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    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