제출 #873301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
873301		PagodePaiva	Joker (BOI20_joker)	C++17	0 / 100	1 ms	4444 KiB

Joker

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

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];
        val[x] %= 2;
        pai[x] = p;
        return pai[x];
    }

    void join(int a, int b){
        int va, vb;
        find(a); find(b);
        va = val[a];
        vb = val[b];
        int sa = a, sb = b;
        a = find(a);
        b = find(b);

        if(sz[a] > sz[b]){ 
            swap(a, b);
            swap(va, vb);
            swap(sa, sb);
        }

        pai[a] = b;
        sz[b] += sz[a];
        val[a] = (((va+vb) % 2) == 0 ? 1 : 0);
    }

    bool query(int a, int b){
        find(a);find(b);
        // cout << a << ' ' << pai[a] << ' ' << val[a] << '\n' << b << ' ' << pai[b] << ' ' << val[b] << '\n';
        if(((val[a] + val[b]) % 2) == 0) return true;
        return false;
    }
} dsu;

vector <pair <int, int>> arestas;
vector <array <int, 3>> query;
int resp[N];

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    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);
        }

        while(con < q and i == query[con][1]){
            if(res){
                resp[query[con][2]] = 1;
            }
            else{
                resp[query[con][2]] = 0;
            }
            con++;
        }
    }

    for(auto &x : query){
        x[0] = x[2];
    }

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

    for(int i = 1;i <= n;i++){
        cout << i << ' ' << dsu.val[i] << ' ' << dsu.pai[i] << '\n';
    }

    cout << '\n';
    for(auto x : query){
        if(resp[x[0]] == 1){
            cout << "YES\n";
        }
        else{
            cout << "NO\n";
        }
    }

    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