Submission #1111356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111356		hmm789	Drivers (BOI24_drivers)	C++14	100 / 100	132 ms	23980 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long 

int p[200000];
int root(int x) {
	if(p[x] == x) return x;
	else return p[x] = root(p[x]);
}
void merge(int x, int y) {
	x = root(x); y = root(y);
	if(x == y) return;
	p[x] = y;
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m, q, x, y, w;
	cin >> n >> m >> q;
	vector<tuple<int, int, int>> edg;
	for(int i = 0; i < m; i++) {
		cin >> x >> y >> w;
		x--; y--;
		edg.push_back({w, x, y});
	}
	sort(edg.begin(), edg.end());
	tuple<int, int, int, int> qry[q];
	int ans[q];
	for(int i = 0; i < q; i++) {
		cin >> x >> y >> w;
		x--; y--;
		qry[i] = {w, i, x, y};
	}
	sort(qry, qry+q);
	for(int i = 0; i < n; i++) p[i] = i;
	int idx = 0;
	for(int i = 0; i < q; i++) {
		int x, y, w, ind;
		tie(w, ind, x, y) = qry[i];
		while(idx < edg.size() && get<0>(edg[idx]) <= w) {
			int nx = get<1>(edg[idx]);
			int ny = get<2>(edg[idx]);
			merge(nx, ny);
			idx++;
		}
		ans[ind] = root(x) == root(y);
	}
	for(int i = 0; i < q; i++) {
		if(ans[i]) cout << "TAIP\n";
		else cout << "NE\n";
	}
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:41:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   while(idx < edg.size() && get<0>(edg[idx]) <= w) {
      |         ~~~~^~~~~~~~~~~~

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