Submission #1159857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159857		Gr1sen	Drivers (BOI24_drivers)	C++20	100 / 100	173 ms	23208 KiB

Main

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<queue>

using namespace std;

#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define ppi pair<pi, pi>
#define vp vector<pi>
#define vvp vector<vp>
#define MP make_pair
#define pq priority_queue<ppi>

vvp Adj;
vi P;
pq Q;
vp U;

int find(int a) {
	//cerr << "find " << a << endl;
	return P[a] == -1 ? a : P[a] = find(P[a]);
}

void uninon(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	P[a] = b;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, u; cin >> n >> m >> u;
	Adj = vvp(n);
	U = vp(u);
	P = vi(n, -1);
	vi Ans(u, -1);
	for (int i = 0; i < m; i++) {
		int x, y, t; cin >> x >> y >> t; x--; y--;
		Adj[x].push_back({t, y});
		Adj[y].push_back({t, x});
		Q.push({{-t, 1}, {x, y}});
	}
	for (int i = 0; i < u; i++) {
		int a, b, p; cin >> a >> b >> p; a--; b--;
		Q.push({{-p, 0}, {i, -1}});
		U[i] = {a, b};
	}
	while (!Q.empty()) {
		int c = Q.top().first.first, t = Q.top().first.second;
		//cerr << c << " " << t << endl;
		if (t == 1) {
			uninon(Q.top().second.first, Q.top().second.second);
			Q.pop();
			continue;
		}
		int id = Q.top().second.first;
		//cerr << id << endl;
		Ans[id] = find(U[id].first) == find(U[id].second);
		Q.pop();
	}
	for (auto i : Ans) {
		cout << (i?"TAIP":"NE") << "\n";
	}
}

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