oj.uz

Submission #1107219

# Submission time Handle Problem Language Result Execution time Memory
1107219 2024-11-01T03:04:48 Z BF001 Joker (BOI20_joker) C++17
25 / 100
 186 ms 14776 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define N 200005
#define fi first
#define se second

typedef pair<int, int> ii;

int n, m, q, siz[2 * N], par[2 * N], u[N], v[N], ma[N];
vector<ii> vec;
 
int find(int u){
    if (u == par[u]) return u;
    return find(par[u]);
}

void unin(int u, int v){
    u = find(u); v = find(v);
    if (u == v) return;
    if (siz[u] < siz[v]) swap(u, v);
    par[v] = u;
    siz[u] += siz[v];
    vec.push_back({u, v});
}

void rollbak(int si){
    while ((int)vec.size() > si){
        ii tmp = vec.back();
        vec.pop_back();
        par[tmp.se] = tmp.se;
        siz[tmp.fi] -= siz[tmp.se];
    }
}

void dnc(int l, int r, int opl, int opr, int ok){
    if (l > r) return;
    int mid = (l + r) >> 1;
    int odd = ok;
    int sii = (int) vec.size();
    for (int i = l; i <= mid; i++){
        unin(u[i], v[i] + n);
        unin(u[i] + n, v[i]);
        if (find(u[i]) == find(u[i] + n)) odd = 1;
    }
    int rt = -1;
    int si = (int) vec.size();
    int tmp = odd;
    for (int i = opr; i >= max(opl, mid); i--){
        if (odd){
            rt = i;
            break;
        }
        unin(u[i], v[i] + n);
        unin(u[i] + n, v[i]);
        if (find(u[i]) == find(u[i] + n)) odd = 1;
    }
    ma[mid] = rt;
    rollbak(si);
    odd = tmp;
    dnc(mid + 1, r, rt, opr, odd);
    rollbak(sii);
    odd = ok;
    for (int i = opr; i > rt; i--){
        unin(u[i], v[i] + n);
        unin(u[i] + n, v[i]);
        if (find(u[i]) == find(u[i] + n)) odd = 1;
    }
    dnc(l, mid - 1, opl, rt, odd);
    rollbak(sii);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++){
        cin >> u[i] >> v[i];
    }

    for (int i = 1; i <= 2 * n; i++){
        siz[i] = 1;
        par[i] = i;
    }

    dnc(1, m, 1, m, 0);

    while (q--){
        int l, r;
        cin >> l >> r;
        if (ma[l] >= r){
            cout << "YES\n";
        }
        else cout << "NO\n";
    }
 
    return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 134 ms 11968 KB Output is correct
4 Correct 137 ms 14540 KB Output is correct
5 Correct 110 ms 14776 KB Output is correct
6 Correct 121 ms 11968 KB Output is correct
7 Correct 132 ms 11968 KB Output is correct
8 Correct 149 ms 9944 KB Output is correct
9 Correct 158 ms 11456 KB Output is correct
10 Correct 183 ms 14524 KB Output is correct
11 Correct 144 ms 11664 KB Output is correct
12 Correct 171 ms 14516 KB Output is correct
13 Correct 142 ms 9416 KB Output is correct
14 Correct 163 ms 10432 KB Output is correct
15 Correct 177 ms 14264 KB Output is correct
16 Correct 186 ms 14776 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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