oj.uz

Submission #1107220

# Submission time Handle Problem Language Result Execution time Memory
1107220 2024-11-01T03:15:03 Z BF001 Joker (BOI20_joker) C++17
25 / 100
 200 ms 11968 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 = max(opl, mid) - 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 4440 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 4440 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 4440 KB Output is correct
3 Correct 121 ms 8140 KB Output is correct
4 Correct 200 ms 11968 KB Output is correct
5 Correct 99 ms 11712 KB Output is correct
6 Correct 120 ms 8184 KB Output is correct
7 Correct 122 ms 8140 KB Output is correct
8 Correct 153 ms 6480 KB Output is correct
9 Correct 155 ms 8152 KB Output is correct
10 Correct 183 ms 11888 KB Output is correct
11 Correct 130 ms 8160 KB Output is correct
12 Correct 159 ms 11720 KB Output is correct
13 Correct 154 ms 5576 KB Output is correct
14 Correct 150 ms 6340 KB Output is correct
15 Correct 184 ms 11464 KB Output is correct
16 Correct 200 ms 11968 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 4440 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 4440 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 4440 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 -