제출 #1257442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257442		TIN	Drivers (BOI24_drivers)	C++17	100 / 100	137 ms	28020 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int N, M, Q;
	cin >> N >> M >> Q;
	vector<pair<int,pair<int,int>>> edges;
	for (int i = 0; i < M; i++) {
		int u, v, t;
		cin >> u >> v >> t;
		--u, --v;
		edges.push_back({t, {u, v}});
	}
	vector<pair<pair<int,int>,int>> actual_queries(Q);
	for (int i = 0; i < Q; i++) {
		int a, b, p;
		cin >> a >> b >> p;
		--a, --b;
		actual_queries[i] = {{a, b}, p};
	}
	int maxT = 0;
	vector<vector<int>> e_id;
	vector<vector<int>> q_id;
	{
		vector<int> vec;
		for (int i = 0; i < M; i++) vec.push_back(edges[i].first);
		for (int i = 0; i < Q; i++) vec.push_back(actual_queries[i].second);
		sort(vec.begin(), vec.end());
		vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
		maxT = (int) vec.size();
		e_id.resize(maxT);
		q_id.resize(maxT);
		for (int i = 0; i < M; i++) {
			int eid = lower_bound(vec.begin(), vec.end(), edges[i].first) - vec.begin();
			e_id[eid].push_back(i);
		}
		for (int i = 0; i < Q; i++) {
			int qid = lower_bound(vec.begin(), vec.end(), actual_queries[i].second) - vec.begin();
			q_id[qid].push_back(i);
		}
	}
	vector<int> par(N), sz(N);
	for (int i = 0; i < N; i++) par[i] = i, sz[i] = 1;
	function<int(int)> find_set;
	find_set = [&](int u) -> int {
		if (par[u] == u) return u;
		return par[u] = find_set(par[u]);
	};
	auto union_set = [&](int u, int v) -> void {
		u = find_set(u);
		v = find_set(v);
		if (u == v) return;
		if (sz[u] < sz[v]) swap(u, v);
		sz[u] += sz[v];
		par[v] = u;
		return;
	};
	vector<bool> ans(Q);
	for (int t = 0; t < maxT; t++) {
		for (int eid : e_id[t]) union_set(edges[eid].second.first, edges[eid].second.second);
		for (int qid : q_id[t]) ans[qid] = (find_set(actual_queries[qid].first.first) == find_set(actual_queries[qid].first.second));
	}
	for (int i = 0; i < Q; i++) cout << (ans[i] ? "TAIP" : "NE") << '\n';
	return 0;
}

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