Submission #575564

#	Time	Username	Problem	Language	Result	Execution time	Memory
575564		talant117408	Joker (BOI20_joker)	C++17	100 / 100	316 ms	14380 KiB

Joker

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

const int N = 2e5+7;
struct query {
    int l, r;
    int index;
    query() {
        l = r = 0;
        index = -1;
    }
};
struct DSU {
    vector <int> link, saizu, color;
    int odd_cycles;
    vector <tuple <int, int, bool>> st;
    
    DSU() {}
    DSU(int n) {
        link.resize(n+1);
        saizu.resize(n+1);
        color.resize(n+1);
        odd_cycles = 0;
        for (int i = 1; i <= n; i++) {
            link[i] = i;
            saizu[i] = 1;
            color[i] = 0;
        }
    }
    int find(int n) {
        if (n == link[n]) return n;
        return find(link[n]);
    }
    int find_color(int n) {
        int x = color[n];
        while (n != link[n]) {
            n = link[n];
            x ^= color[n];
        }
        return x;
    } 
    void unite(int a, int b) {
        int u = a, v = b;
        a = find(a); b = find(b);
        st.emplace_back(a, b, find_color(u) == find_color(v));
        if (a == b) {
            if (find_color(u) == find_color(v)) {
                odd_cycles++;
            }
        }
        else {
            if (saizu[a] < saizu[b]) swap(a, b);
            if (find_color(u) == find_color(v)) color[b] ^= 1;
            color[b] ^= color[a];
            saizu[a] += saizu[b];
            link[b] = a;
        }
    }
    void rollback() {
        auto a = get<0>(st.back()), b = get<1>(st.back());
        auto odd = get<2>(st.back());
        st.pop_back();
        if (a == b) {
            if (odd) {
                odd_cycles--;
            }
        }
        else {
            if (saizu[a] < saizu[b]) swap(a, b);
            saizu[a] -= saizu[b];
            link[b] = b;
        }
    }
    void remove(int x) {
        while (x--) {
            assert(!st.empty());
            rollback();
        }
    }
};
int opt[N], from[N], to[N];
DSU dsu;

void dnc(int l1, int l2, int r1, int r2) {
    if (l1 > l2) return;
    int lmid = (l1+l2) >> 1;
    for (int i = l1; i < lmid; i++) {
        dsu.unite(from[i], to[i]);
    }
    
    opt[lmid] = r2;
    while (!dsu.odd_cycles && opt[lmid] >= r1) {
        dsu.unite(from[opt[lmid]], to[opt[lmid]]);
        opt[lmid]--;
    }
    dsu.remove(r2-opt[lmid]);
    
    dsu.unite(from[lmid], to[lmid]);
    dnc(lmid+1, l2, opt[lmid], r2);
    dsu.remove(lmid-l1+1);
    
    for (int i = opt[lmid]+1; i <= r2; i++) {
        dsu.unite(from[i], to[i]);
    }
    dnc(l1, lmid-1, r1, opt[lmid]);
    dsu.remove(r2-opt[lmid]);
}

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    dsu = DSU(n);
    for (int i = 1; i <= m; i++) {
        cin >> from[i] >> to[i];
    }
    dnc(1, m, 1, m);
    while (q--) {
        int l, r;
        cin >> l >> r;
        if (r <= opt[l]) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}
/*
6 8 8
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
1 3
1 7
1 5
1 1
1 6
1 4
1 2
1 8 

6 8 6
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
1 5
2 5
3 5
4 5
6 7
6 8

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: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 22 / 22
• Subtask 6: 29 / 29