Submission #1107227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107227		BF001	Joker (BOI20_joker)	C++17	100 / 100	258 ms	16116 KiB

Joker

#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;
    unin(u[mid], v[mid] + n);
    unin(u[mid] + n, v[mid]);
    if (find(u[mid]) == find(u[mid] + n)) odd = 1;
    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: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 22 / 22
• Subtask 6: 29 / 29