oj.uz

Submission #873292

# Submission time Handle Problem Language Result Execution time Memory
873292 2023-11-14T19:12:59 Z PagodePaiva Joker (BOI20_joker) C++17
0 / 100
 171 ms 12220 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 171 ms 12220 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -