Участник:Kozlinskii/ADABRANC

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/ADABRANC/ c++14(gcc 8.3)

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
const int MAX_Q = 300010;
 
struct vertex{
    int type;
    int id;
    int a;
    int b;
    int weight;
 
    vertex(int type, int id, int a, int b, int weight):
        type(type), id(id), a(a), b(b), weight(weight) {}
 
    bool operator < (const vertex other) const {
        if (weight != other.weight) {
            return weight > other.weight;
        } else {
            return type < other.type;
        }
    }
};
 
 
int N, M, Q;
int parent[MAX_Q];
int componentSize[MAX_Q];
int result[MAX_Q];
vector<vertex> vertexes;
 
int findRoot(int node) {
    if (parent[node] == node) {
        return node;
    } else {
        parent[node] = findRoot(parent[node]);
        return parent[node];
    }
}
 
void mergeNodes(int x, int y) {
    int rootX = findRoot(x);
    int rootY = findRoot(y);
    if (rootX == rootY) {
        return;
    }
    if (rand() & 1) {
        swap(rootX, rootY);
    }
    parent[rootY] = rootX;
    componentSize[rootX] += componentSize[rootY];
    componentSize[rootY] = 0;
}
 
int main() {
    cin >> N >> M >> Q;
    for (int i = 1; i <= N; ++i) {
        parent[i] = i;
        componentSize[i] = 1;
    }
 
    for (int i = 0; i < M; ++i) {
        int a, b, l;
        cin >> a >> b >> l;
        ++a;
        ++b;
        vertexes.push_back(vertex(1, -1, a, b, l));
    }
 
    for (int i = 0; i < Q; ++i) {
        int a, x;
        cin >> a >> x;
        ++a;
        vertexes.push_back(vertex(2, i, a, -1, x));
    }
 
    sort(vertexes.begin(), vertexes.end());
    for (auto v : vertexes) {
        if (v.type == 1) {
            mergeNodes(v.a, v.b);
        }
        else {
            result[v.id] = componentSize[findRoot(v.a)];
        }
    }
 
    for (int i = 0; i < Q; ++i) {
        cout << result[i] << "\n";
    }
    return 0;
}