oj.uz

Submission #873301

# Submission time Handle Problem Language Result Execution time Memory
873301 2023-11-14T19:44:13 Z PagodePaiva Joker (BOI20_joker) C++17
0 / 100
 1 ms 4444 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -