Submission #877226

#	Time	Username	Problem	Language	Result	Execution time	Memory
877226		socpite	Joker (BOI20_joker)	C++14	14 / 100	2058 ms	8704 KiB

Joker

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 5;

int up[maxn], par[maxn];

int n, m, q;

int Find(int x){
    if(!up[x])return x;
    else{
        int tmp = up[x];
        up[x] = Find(tmp);
        par[x]^=par[tmp];
        return up[x];
    }
}

bool bad = 0;

vector<int> undo;

void Union(int a, int b){
    undo.push_back(a);
    undo.push_back(b);
    int ra = Find(a), rb = Find(b);
    if(ra == rb){
        // cout << ra << endl;
        // cout << par[a] << " " << par[b] << endl;
        if(par[a] == par[b])bad = 1;
    }
    else{
        up[rb]= ra;
        par[rb]=par[a]^par[b]^1;
    }
}

void rs() {
    bad = 0;
    for(auto v: undo)up[v] = par[v] = 0;
    undo.clear();
}

int U[maxn], V[maxn];
int bound[maxn];

void dnc(int l, int r, int ql, int qr) {
    if(l > r)return;
    int mid = (l+r)>>1;
    // cout << mid << " " << ql << " " << qr << endl;
    rs();
    int ans = qr;
    if(ql < mid){
        for(int i = mid; i < ql; i++)Union(U[i], V[i]);
    }
    for(int i = max(mid, ql); i < qr; i++){
        Union(U[i], V[i]);
        if(bad){
            ans = i;
            break;
        }
    }
    // cout << ans << endl;
    bound[mid] = ans;
    dnc(l, mid-1, ql, ans);
    dnc(mid+1, r, ans, qr);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++)cin >> U[i] >> V[i];
    for(int i = m+1; i <= 2*m; i++){
        U[i] = U[i-m];
        V[i] = V[i-m];
    }
    // dnc(1, 2*m, 1, 2*m+1);
    for(int i = 1; i <= m+1; i++){
        rs();
        bound[i] = 2*m+1;
        for(int j = i; j <= 2*m; j++){
            Union(U[j], V[j]);
            if(bad){
                bound[i] = j;
                break;
            }
        }
    }
    // for(int i = 1; i <= 2*m; i++)cout << i << " " << bound[i] << endl;
    while(q--){
        int l, r;
        cin >> l >> r;
        if(l + m - 1 >= bound[r+1])cout << "YES";
        else cout << "NO";
        cout << "\n";
    }
}

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