Submission #1093517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093517		Zero_OP	Joker (BOI20_joker)	C++14	0 / 100	61 ms	9812 KiB

Joker

#include "bits/stdc++.h"

using namespace std;

const int MAX = 2e5 + 5;

int n, m, q, f[MAX], eu[MAX], ev[MAX], lab[MAX], d[MAX];
bool exist_odd_cycle;
struct state{
    int u, pu, v, pv;
};

stack<state> states;

void init(int n){
    fill(lab, lab + n, -1);
    fill(d, d + n, 0);
    exist_odd_cycle = false;
}

int find_root(int u){
    return lab[u] < 0 ? u : find_root(lab[u]);
}

int find_dist(int u){
    return lab[u] < 0 ? 0 : d[u] ^ find_dist(lab[u]);
}

bool unite(int u, int v){
    int l = find_dist(u) ^ find_dist(v) ^ 1;
    u = find_root(u); v = find_root(v);

    if(u == v){
        if(l) exist_odd_cycle = true;
        return false;
    }

    if(lab[u] > lab[v]) swap(u, v);
    states.push({u, lab[u], v, lab[v]});
    lab[u] += lab[v];
    lab[v] = u;
    d[v] = l;
    return true;
}

void rollback(){
    assert(!states.empty());
    state st = states.top(); states.pop();
    lab[st.u] = st.pu;
    lab[st.v] = st.pv;
    d[st.v] = 0;
    d[st.u] = 0;
}

void solve(int l, int r, int optL, int optR){
    if(l > r || optL > optR) return;
    bool check_before = exist_odd_cycle;

    int num = 0;
    int mid = l + r >> 1;

    for(int i = l; i < mid; ++i){
//        cout << "in advance : " << eu[i] << ' ' << ev[i] << '\n';
        num += unite(eu[i], ev[i]);
    }

    int optMid = 0, nw = 0;
    bool check_after = exist_odd_cycle;
    for(int i = optR; i >= max(optL, mid); --i){
        if(exist_odd_cycle){
            optMid = i;
            break;
        }

        nw += unite(eu[i], ev[i]);
//        cout << "suffix : " << eu[i] << ' ' << ev[i] << '\n';
    }

    assert(num >= 0 && nw >= 0);
//    cout << mid << ' ' << optMid << '\n';
    f[mid] = optMid;
    while(nw--) rollback();
    exist_odd_cycle = check_after;

    num += unite(eu[mid], ev[mid]);
    solve(mid + 1, r, optMid, optR);
    while(num--) rollback();
    exist_odd_cycle = check_before;

    for(int i = optR; i > optMid; --i){
        unite(eu[i], ev[i]);
    }

    solve(l, mid - 1, optL, optMid);
}

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

    if(fopen("task.inp", "r")){
        freopen("task.inp", "r", stdin);
        freopen("task.out", "w", stdout);
    }

    cin >> n >> m >> q;
    for(int i = 1; i <= m; ++i){
        cin >> eu[i] >> ev[i];
        --eu[i], --ev[i];
    }

    init(n);
    for(int i = 1; i <= m; ++i) f[i] = 0;
    solve(1, m, 1, m);

//    for(int i = 1; i <= m; ++i){
//        cout << f[i] << ' ';
//    }
//    cout << '\n';

    while(q--){
        int l, r;
        cin >> l >> r;
        cout << (f[l] >= r ? "YES\n" : "NO\n");
    }

    return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:60:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     int mid = l + r >> 1;
      |               ~~^~~
Joker.cpp: In function 'int main()':
Joker.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen("task.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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