Submission #1283156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283156		abc123	Drivers (BOI24_drivers)	C++20	100 / 100	293 ms	13580 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int t, x, y;
};

struct Query {
    int a, b, p, idx;
};

vector<int> par;

int find(int x) {
    if (par[x] != x) par[x] = find(par[x]);
    return par[x];
}

void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x != y) par[x] = y;
}

int main() {
    int N, M, U;
    cin >> N >> M >> U;
    vector<Edge> edges(M);
    for (int i = 0; i < M; ++i)
        cin >> edges[i].x >> edges[i].y >> edges[i].t;

    vector<Query> queries(U);
    for (int i = 0; i < U; ++i) {
        cin >> queries[i].a >> queries[i].b >> queries[i].p;
        queries[i].idx = i; // preserve order
    }
    sort(edges.begin(), edges.end(), [](Edge a, Edge b){ return a.t < b.t; });
    sort(queries.begin(), queries.end(), [](Query a, Query b){ return a.p < b.p; });

    par.resize(N + 1);
    for (int i = 1; i <= N; ++i) par[i] = i;

    vector<string> answer(U);
    int edge_i = 0;
    for (const auto& q : queries) {
        // Activate all roads <= current p
        while (edge_i < M && edges[edge_i].t <= q.p) {
            unite(edges[edge_i].x, edges[edge_i].y);
            ++edge_i;
        }
        if (find(q.a) == find(q.b)) answer[q.idx] = "TAIP";
        else answer[q.idx] = "NE";
    }
    for (auto& ans : answer) cout << ans << '\n';
}

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