Submission #639604

#	Time	Username	Problem	Language	Result	Execution time	Memory
639604		a_aguilo	Synchronization (JOI13_synchronization)	C++14	0 / 100	614 ms	262144 KiB

synchronization

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40