Submission #1303367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303367		BuiDucManh123	Joker (BOI20_joker)	C++20	14 / 100	2023 ms	165556 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];
    }
};
int u[200009], v[200009];
void Solve(){
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 0; i < m; i++){
        cin >> u[i] >> v[i];
        u[i]--;
        v[i]--;
    }
    if(n <= 2000 && m <= 2000 && q <= 2000){
        while(q--){
            int l, r;
            cin >> l >> r;
            l--; r--;
            DSU dsu(n);
            for(int i = 0; i < l; i++){
                dsu.merge(u[i], v[i]);
            }
            for(int i = r + 1; i < m; i++){
                dsu.merge(u[i], v[i]);
            }
            if(dsu.odd){
                cout << "YES\n";
            }else{
                cout << "NO\n";
            }
        }
    }else{
        vector<vector<int>> ans(min(200, m), vector<int>(m, 0));
        for(int i = 0; i < min(200, m); i++){
            DSU dsu(n);
            for(int j = 0; j < i; j++){
                dsu.merge(u[j], v[j]);
            }
            for(int j = m - 1; j > i; j--){
                dsu.merge(u[j], v[j]);
                ans[i][j - 1] = dsu.odd;
            }
        }
        while(q--){
            int l, r;
            cin >> l >> r;
            l--; r--;
            if(ans[l][r]){
                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:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(TN".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(TN".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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