oj.uz

Submission #639604

# Submission time Handle Problem Language Result Execution time Memory
639604 2022-09-10T17:30:24 Z a_aguilo Synchronization (JOI13_synchronization) C++14
0 / 100
 614 ms 262144 KB 
#include<bits/stdc++.h>

using namespace std;

int N, M, Q;
vector<int> padre, activated;
vector<unordered_set<int>> information;
vector<pair<int, int>> bonds;

int root(int node){
    if(padre[node] == node) return node;
    return root(padre[node]);
}

void synchronise(int nodeA, int nodeB){
    for(auto it = information[nodeA].begin(); it != information[nodeA].end(); ++it){
        information[nodeB].insert(*it);
    }
    for(auto it = information[nodeB].begin(); it != information[nodeB].end(); ++it){
        information[nodeA].insert(*it);
    }
}

void mergeComponents(int nodeA, int nodeB) {
    if(nodeA > nodeB){
        int temp = nodeA;
        nodeA = nodeB;
        nodeB = temp;
    }
    //nodeA, el padre, es siempre de valor mas pequeño
    padre[nodeB] = nodeA;
    nodeA = root(nodeA);
    synchronise(nodeA, nodeB);
}

void separeComponents(int nodeA, int nodeB){
    if(padre[nodeA] == nodeB){
        int temp = nodeA;
        nodeA = nodeB;
        nodeB = temp;
    }
    //A es el padre
    synchronise(nodeB, root(nodeA));
    padre[nodeB] = nodeB;
}

int main(){
    cin >> N >> M >> Q;
    int a, b;
    bonds = vector<pair<int, int>>(N-1);
    for(int i = 1; i < N; ++i) {
        cin >> a >> b;
        a--; b--;
        bonds[i-1] = {a, b};
    }
    padre = vector<int> (N);
    //cout << " a" << endl;
    for(int i = 0; i < N; ++i) padre[i] = i;
    //cout << "a" << endl;
    activated = vector<int>(N-1, 0);
    //cout << "a" << endl;
    information  = vector<unordered_set<int>>(N);
    //cout << " a" << endl;
    for(int i = 0; i < N; ++i) information[i].insert(i);
    //cout << " a " << endl;
    while(M--){
        cin >> a; a--;
        activated[a]^=1;
        if(activated[a]){
            mergeComponents(bonds[a].first, bonds[a].second);
        }
        else{
            separeComponents(bonds[a].first, bonds[a].second);
        }
    }
    while(Q--){
        cin >> a; a--;
        cout << information[a].size() << endl;
    }
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 614 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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