Submission #1303438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303438		BuiDucManh123	Joker (BOI20_joker)	C++20	100 / 100	208 ms	12624 KiB

Joker

#include <bits/stdc++.h>
#define TN ""
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

struct DSU {
    vector<int> par;
    vector<int> rnk;
    vector<int> col;
    int odd;
    stack<array<int, 5>> history;

    DSU(int n) {
        par = vector<int>(n);
        iota(par.begin(), par.end(), 0);
        col = vector<int>(n, 0);
        rnk = vector<int>(n, 0);
        odd = 0;
    }

    pair<int, int> find(int x) {
        int c = col[x];
        while (par[x] != x) {
            x = par[x];
            c ^= col[x];
        }
        return {x, c};
    }

    void merge(int a, int b) {
        auto [pa, ca] = find(a);
        auto [pb, cb] = find(b);
        if (pa != pb) {
            if (rnk[pa] < rnk[pb]) swap(pa, pb);
            int dc = 0, dr = 0;
            if (ca == cb) dc = 1;
            if (rnk[pa] == rnk[pb]) dr = 1;
            par[pb] = pa;
            rnk[pa] += dr;
            col[pb] ^= dc;
            history.push({pa, pb, dr, dc, -1});
        } else if (ca == cb) {
            odd++;
            history.push({0, 0, 0, 0, 1});
        } else {
            history.push({0, 0, 0, 0, 0});
        }
    }

    void Rollback() {
        assert(!history.empty());
        auto t = history.top();
        history.pop();
        if (t[4] >= 0) {
            odd -= t[4];
            return;
        }
        col[t[1]] ^= t[3];
        rnk[t[0]] -= t[2];
        par[t[1]] = t[1];
    }
}dsu(200009);
int u[200009], v[200009], ans[200009];
void dnc(int l, int r, int pre, int suf){
    if(l > r) return;
    if(pre > suf) return;
    int mid = l + (r - l) / 2;
    int siz = dsu.history.size();
    for(int i = l; i <= mid; i++){
        dsu.merge(u[i], v[i]);
    }
    int now = suf;
    int sz = dsu.history.size();
    while(!dsu.odd && now >= pre){
        dsu.merge(u[now], v[now]);
        now--;
    }
    ans[mid] = now + 1;
    while(dsu.history.size() > sz){
        dsu.Rollback();
    }
    dnc(mid + 1, r, now, suf);
    while(dsu.history.size() > siz){
        dsu.Rollback();
    }
    for(int i = suf; i > now; i--){
        dsu.merge(u[i], v[i]);
    }
    dnc(l, mid - 1, pre, now);
}
void Solve(){
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++){
        cin >> u[i] >> v[i];
    }
    int id = m + 1;
    while(!dsu.odd){
        id--;
        dsu.merge(u[id], v[id]);
    }
    ans[0] = id;
    while(dsu.history.size()){
        dsu.Rollback();
    }
    dnc(1, m, 1, m);
    while(q--){
        int l, r;
        cin >> l >> r;
        if(ans[l - 1] >= r + 1){
            cout << "YES\n";
        }else{
            cout << "NO\n";
        }
    }
}
signed main() {
    if(fopen(TN".inp", "r")){
        freopen(TN".inp", "r", stdin);
        freopen(TN".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test = 1;
    //cin >> test;
    while(test--){
        Solve();
    }
    return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(TN".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen(TN".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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