제출 #1159874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159874		fv3	Drivers (BOI24_drivers)	C++20	100 / 100	97 ms	8988 KiB

Main

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, pair<int, int>>> edges;
vector<int> par, sz;

int find(int index) {
    if (par[index] == index) return par[index];
    return par[index] = find(par[index]);
}
struct query {
    int d, a, b, i;

    bool operator<(query other) {
        return d < other.d;
    }
};

void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;

    if (sz[a] < sz[b]) {
        swap(a, b);
    }

    par[b] = a;
    sz[a] += sz[b];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M, Q;
    cin >> N >> M >> Q;

    edges = vector<pair<int, pair<int, int>>>(M);

    par = vector<int>(N);
    sz = vector<int>(N, 1);
    iota(par.begin(), par.end(), 0);

    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        edges[i] = {c, {a, b}};
    }

    sort(edges.begin(), edges.end());
    edges.push_back({(int)(1e9+7), {0, 0}});

    vector<query> queries(Q); 
    for (int q = 0; q < Q; q++) {
        int a, b, d;
        cin >> a >> b >> d;
        a--; b--;
        queries[q] = {d, a, b, q};
    }
    sort(queries.begin(), queries.end());

    vector<int> res(Q);
    int i = 0;
    for (auto q : queries) {
        while (edges[i].first <= q.d) {
            unite(edges[i].second.first, edges[i].second.second);
            i++;
        }
        if (find(q.a) == find(q.b)) {
            res[q.i] = 1;
        } 
    }

    for (auto r : res) {
        cout << (r ? "TAIP" : "NE") << "\n";
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 23 / 23
• Subtask 5: 45 / 45