Submission #1093567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093567		Zero_OP	Joker (BOI20_joker)	C++14	100 / 100	248 ms	15164 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 x, y;
};

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){
        states.push({-1, exist_odd_cycle});
        if(l) exist_odd_cycle = true;
        return false;
    }

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

int snap(){
    return (int)states.size();
}

void rollback(){
    if(states.top().x == -1){
        exist_odd_cycle = states.top().y;
    } else{
        lab[states.top().x] = states.top().y;
        d[states.top().x] = 0;
    }
    states.pop();
}

void back_to(int k){
    while((int)states.size() > k){
        rollback();
    }
}

void solve(int l, int r, int optL, int optR){
    if(l > r || optL > optR) return;
    int curSnap = snap();
    int mid = l + r >> 1;

    for(int i = l; i < mid; ++i){
        unite(eu[i], ev[i]);
    }

    int optMid = mid - 1, nxtSnap = snap();
    for(int i = optR; i >= max(optL, mid); --i){
        if(exist_odd_cycle){
            optMid = i;
            break;
        }

        unite(eu[i], ev[i]);
    }

    f[mid] = optMid;
    back_to(nxtSnap);

    unite(eu[mid], ev[mid]);
    solve(mid + 1, r, optMid, optR);
    back_to(curSnap);

    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);

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

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