Submission #904829

#	Time	Username	Problem	Language	Result	Execution time	Memory
904829		LOLOLO	Joker (BOI20_joker)	C++17	100 / 100	474 ms	38720 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 3e5 + 100;
int p[N], s[N], a[N], b[N], odd[N], g[N], lst[N];

vector < vector <int>> action;

int find(int n) {
    if (p[n] == 0)
        return n;

    return find(p[n]);
}

int get(int a) {
    if (p[a] == 0)
        return 0;

    return odd[a] ^ get(p[a]);
}

bool check(int a, int b) {
    return find(a) == find(b) && get(a) == get(b);
}

void upsz(int a, int b) {
    action.pb({0, a, s[a]});
    s[a] = b;
}

void uppar(int a, int b) {
    action.pb({1, a, p[a]});
    p[a] = b;
}

void upodd(int a, int b) {
    action.pb({2, a, odd[a]});
    odd[a] = b;
}

void unite(int a, int b) {
    int x = get(a), y = get(b);
    a = find(a);
    b = find(b);
    if (a == b)
        return;

    if (s[a] < s[b])
        swap(a, b);

    uppar(b, a);
    upodd(b, x ^ y ^ 1);

    if (s[a] == s[b])
        upsz(a, s[a] + 1);
}

void rollback(int x) {
    while (sz(action) > x) {
        auto t = action.back();
        action.pop_back();
        if (t[0] == 0) {
            s[t[1]] = t[2];
        }

        if (t[0] == 1) {
            p[t[1]] = t[2];
        }

        if (t[0] == 2) {
            odd[t[1]] = t[2];
        }
    }
}

void dnc(int l, int r, int l1, int r1) {
    if (l > r)
        return;

    if (l1 == r1) {
        for (int i = l; i <= r; i++)
            lst[i] = l1;
        return;
    }
    int tmp1 = sz(action);
    int m = (l + r) / 2;

    for (int i = l; i < m; i++) {
        unite(a[i], b[i]);
    }

    int tmp2 = sz(action);

    for (int i = r1; i >= max(m, l1); i--) {
        if (check(a[i], b[i])) {
            lst[m] = i;
            break;
        }

        unite(a[i], b[i]);
    }                              

    rollback(tmp2);
    if (m < r) {
        unite(a[m], b[m]);
        dnc(m + 1, r, max(m + 1, lst[m]), r1);
    }

    rollback(tmp1);
    if (l < m) {
        for (int i = r1; i > lst[m]; i--) {
            unite(a[i], b[i]);
        }

        dnc(l, m - 1, l1, lst[m]);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m, q;
    cin >> n >> m >> q;

    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i];
    }

    ll v = 1;
    for (int i = 1; i <= m; i++) {
        if (check(a[i], b[i])) {
            for (int j = i + 1; j <= m; j++) {
                lst[j] = m + 1;
            }

            v = i;
            break;
        }

        unite(a[i], b[i]);
    }

    rollback(0);
    if (v <= m)
        dnc(1, v, 1, m);

    while (q--) {
        int l, r;
        cin >> l >> r;

        if (r < lst[l]) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    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