Submission #1111965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111965		gohchingjayk	Drivers (BOI24_drivers)	C++17	100 / 100	261 ms	14376 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using i64 = int64_t;

struct Road {
    int from;
    int to;
    int length;
};

struct Query {
    int from;
    int to;
    int length;
    int original;
};

Road roads[200000];
Query queries[200000];
int parent[200001];
bool result[200000];

int findparent(int i) {
    return parent[i] = (i == parent[i] ? i : findparent(parent[i]));
}

int main() {
    int n_cities, n_roads, n_queries;
    cin >> n_cities >> n_roads >> n_queries;

    for (int i = 0; i < 200001; ++i) parent[i] = i;

    for (int i = 0; i < n_roads; ++i) {
        int from, to, length;
        cin >> from >> to >> length;
        roads[i] = Road{.from = from, .to = to, .length = length};
    }

    for (int i = 0; i < n_queries; ++i) {
        int from, to, length;
        cin >> from >> to >> length;
        queries[i] = Query{.from = from, .to = to, .length = length, .original = i};
    }

    sort(roads, roads + n_roads, [&](const Road &a, const Road &b){ return a.length < b.length; });
    sort(queries, queries + n_queries, [&](const Query &a, const Query &b){ return a.length < b.length; });

    int curr_road = 0;
    for (int i = 0; i < n_queries; ++i) {
        Query query = queries[i];

        for (; curr_road < n_roads; ++curr_road) {
            if (roads[curr_road].length > query.length) break;
            int f = roads[curr_road].from;
            int t = roads[curr_road].to;
            parent[findparent(f)] = findparent(t);
        }

        result[query.original] = findparent(query.from) == findparent(query.to);
    }

    for (int i = 0; i < n_queries; ++i) {
        cout << (result[i] ? "TAIP" : "NE");
        cout << "\n";
    }
}

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