제출 #559767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
559767		hoanghq2004	Joker (BOI20_joker)	C++14	100 / 100	928 ms	65996 KiB

Joker

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define HaiYen

using namespace std;

const int N = 4e5 + 10;

int n, m, q, last[N], ti, num;
int par[N], sz[N];

struct edge {
    int u, v;
} e[N];

struct version {
    int ti, u, par, sz;
} old[N * 40];

int ok[N];

inline int Find(int u) {
    if (u == par[u]) return u;
    old[num++] = {ti, u, par[u], sz[u]};
    return par[u] = Find(par[u]);
}

inline void Union(int u, int v) {
    if ((u = Find(u)) == (v = Find(v))) return;
    old[num++] = {ti, u, par[u], sz[u]};
    old[num++] = {ti, v, par[v], sz[v]};
    if (sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    par[v] = u;
}

inline void rollback() {
    while (num && old[num - 1].ti == ti) {
        auto [_ti, u, _par, _sz] = old[--num];
        par[u] = _par, sz[u] = _sz;
    }
    --ti;
}

struct dta {
    int L, R, u, v;
};

inline void new_v() {
    ++ti;
    ok[ti] = ok[ti - 1];
}

inline void merge(int u, int v) {
    Union(u << 1 ^ 0, v << 1 ^ 1);
    Union(u << 1 ^ 1, v << 1 ^ 0);
    if (Find(u << 1 ^ 0) == Find(u << 1 ^ 1)) ok[ti] = 1;
    if (Find(v << 1 ^ 0) == Find(v << 1 ^ 1)) ok[ti] = 1;
}

inline void divide(int L, int R, int from, int to) {
    if (L > R) return;
    int mid = L + R >> 1;
    new_v();
    for (int i = L; i <= mid; ++i) merge(e[i].u, e[i].v);
    new_v();
    for (int i = to; i >= from; --i) {
        merge(e[i].u, e[i].v);
        if (ok[ti]) {
            last[mid] = i;
            break;
        }
    }
    rollback();
    divide(mid + 1, R, last[mid], to);
    rollback();
    new_v();
    for (int i = to; i > last[mid]; --i) merge(e[i].u, e[i].v);
    divide(L, mid - 1, from, last[mid]);
    rollback();
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v;
    e[m + 1] = {n + 1, n + 2};
    e[0] = {n + 1, n + 2};
    for (int i = 1; i <= 2 * n + 4; ++i) par[i] = i, sz[i] = 1;
    divide(0, m, 1, m + 1);
    while (q--) {
        int l, r;
        cin >> l >> r;
        if (last[l - 1] >= r + 1) cout << "YES\n";
        else cout << "NO\n";
    }
}

컴파일 시 표준 에러 (stderr) 메시지

Joker.cpp: In function 'void rollback()':
Joker.cpp:40:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |         auto [_ti, u, _par, _sz] = old[--num];
      |              ^
Joker.cpp: In function 'void divide(int, int, int, int)':
Joker.cpp:64:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     int mid = L + R >> 1;
      |               ~~^~~

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