Submission #1144583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144583		keaucucal	Drivers (BOI24_drivers)	C++20	100 / 100	231 ms	7432 KiB

Main

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

struct DSU {
	vector<int> boss;
	DSU(int n) : boss(n + 1) {
		for (int i = 1; i <= n; i++) {
			boss[i] = i;
		}
	}

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

	void join(int a, int b) {
		a = find(a), b = find(b);
		boss[a] = b;
	}

	bool same(int a, int b) {
		return find(a) == find(b);
	}
};

int main() {
	int n, m, u;
	cin >> n >> m >> u;
	vector<pair<int, pair<int, int>>> adj(m), req(u);
	for (int i = 0; i < m; i++) {
		int x, y, t;
		cin >> x >> y >> t;
		adj[i] = make_pair(t, make_pair(x, y));
	}
	sort(adj.begin(), adj.end());

	for (int i = 0; i < u; i++) {
		int a, b, p;
		cin >> a >> b >> p;
		req[i] = make_pair(p, make_pair(a, b));
	}

	vector<int> ind(u);
	iota(ind.begin(), ind.end(), 0);
	sort(ind.begin(), ind.end(), [&](int a, int b) {
		return req[a].first < req[b].first;
	});

	vector<bool> ans(u);
	int cur = 0;
	DSU dsu(n);
	for (int i = 0; i < u; i++) {
		int p = req[ind[i]].first;
		while (cur < m && adj[cur].first <= p) {
			dsu.join(adj[cur].second.first, adj[cur].second.second);
			cur++;
		}
			
		ans[ind[i]] = dsu.same(req[ind[i]].second.first, req[ind[i]].second.second); // or false
	}

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

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