oj.uz

Submission #1093517

# Submission time Handle Problem Language Result Execution time Memory
1093517 2024-09-27T02:00:33 Z Zero_OP Joker (BOI20_joker) C++14
0 / 100
 61 ms 9812 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 61 ms 9812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -