Submission #947980

#	Time	Username	Problem	Language	Result	Execution time	Memory
947980		dimashhh	Joker (BOI20_joker)	C++17	49 / 100	2005 ms	22924 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 5, MOD = 998244353;

int p[N],sz[N],n,m,q,d[N];
void reset(){
    for(int i = 1;i <= n;i++){
        sz[i] = 1;
        p[i] = i;
        d[i] = 0;
    }
}
pair<int, int> get(int v) {
//    cerr << v << ' ' << p[v] << '\n';
    if(p[v] == v){
        return {v,0};
    }
    pair<int,int> x = get(p[v]);
    p[v] = x.first;
    d[v] += x.second;
    return {p[v],d[v]};
}
bool merge(int a,int b){
    pair<int,int> x = get(a),y = get(b);
    if(sz[x.first] < sz[y.first]){
        swap(x,y);
    }
    a = x.first;
    b = y.first;
    if(a == b){
        if(x.second % 2 == y.second % 2){
            return false;
        }
        return true;
    }
    p[b] = a;
    sz[a] += sz[b];
    d[b] = (x.second % 2 == y.second % 2);
    return true;
}
int x[N],y[N];
vector<pair<int,int>> qr[N];
vector<int> ids[N];
bool ans[N];
void test(){
    cin >> n >> m >> q;
    for(int i = 1;i <= m;i++){
        cin >> x[i] >> y[i];
    }
    for(int i = 1;i <= q;i++){
        int l,r;
        cin >> l >> r;
        qr[l].push_back({i,r});
    }
    for(int i = 1;i <= m;i++){
        if(qr[i].size()){
            reset();
        }else continue;
        for(int j = i;j <= m;j++){
            ids[j].clear();
        }
        for(auto [id,j]:qr[i]){
            ids[j].push_back(id);
        }
        bool is = true;
        for(int j = 1;j < i;j++) {
            is &= merge(x[j],y[j]);
        }
        for(int j = m;j >= i;j--){
            for(int k:ids[j]){
                ans[k] = (!is);
            }
            is &= merge(x[j],y[j]);
        }
    }
    for(int i = 1;i <= q;i++){
        cout << (ans[i] ? "YES\n":"NO\n");
    }
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int T = 1;
//    cin >> T;
    while(T--){
        test();
    }
}

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