oj.uz

Submission #873321

# Submission time Handle Problem Language Result Execution time Memory
873321 2023-11-14T20:10:25 Z PagodePaiva Joker (BOI20_joker) C++17
0 / 100
 2000 ms 6260 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 j = 1;j <= q;j++){
        int a, b;
        cin >> a >> b;
        dsu.init(n);
        bool res = false;

        for(int i = 1;i < a;i++){
            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);
            }
        }

        for(int i = b+1;i <= m;i++){
            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(res){
            cout << "YES\n";
        }
        else{
            cout << "NO\n";
        }
    }
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Incorrect 1 ms 4440 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Incorrect 1 ms 4440 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Execution timed out 2057 ms 6260 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Incorrect 1 ms 4440 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Incorrect 1 ms 4440 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Incorrect 1 ms 4440 KB Output isn't correct
9 Halted 0 ms 0 KB -