Submission #873292

#	Time	Username	Problem	Language	Result	Execution time	Memory
873292		PagodePaiva	Joker (BOI20_joker)	C++17	0 / 100	171 ms	12220 KiB

Joker

#include<bits/stdc++.h>
#define N 200010

using namespace std;

const int B = 500;
int n, m, q;

struct DSU{
    int pai[N], sz[N], val[N];

    void init(int n){
        for(int i = 1;i <= n;i++){
            pai[i] = i;
            sz[i] = 1;
            val[i] = 0;
        }
    }

    int find(int x){
        if(x == pai[x]) return x;
        int p = find(pai[x]);
        val[x] += val[p];
        pai[x] = p;
        return pai[x];
    }

    void join(int a, int b){
        a = find(a);
        b = find(b);

        if(sz[a] > sz[b]) swap(a, b);

        pai[a] = b;
        sz[b] += sz[a];
        val[a] = 1;
    }

    bool query(int a, int b){
        find(a);find(b);
        if(((val[a] + val[b]) % 2) == 0) return true;
        return false;
    }
} dsu;

vector <pair <int, int>> arestas;
vector <array <int, 3>> query;

int main(){
    cin >> n >> m >> q;

    for(int i = 1;i <= m;i++){
        int a, b;
        cin >> a >> b;
        arestas.push_back({a, b});
    }

    for(int i = 1;i <= q;i++){
        int a, b;
        cin >> a >> b;
        query.push_back({a, b, i});
    }

    sort(query.begin(), query.end());

    int con = 0;
    bool res = false;
    dsu.init(n);

    for(int i = 1;i <= m;i++){
        if(con == q) break;

        if(dsu.find(arestas[i-1].first) == dsu.find(arestas[i-1].second)){
            if(dsu.query(arestas[i-1].first, arestas[i-1].second)){
                res = true;
            }
        }

        else{
            dsu.join(arestas[i-1].first, arestas[i-1].second);
        }

        if(i == query[con][1]){
            if(res){
                cout << "YES\n";
            }
            else{
                cout << "NO\n";
            }
            con++;
        }
    }

    return 0;
}

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