Submission #5278

#	Time	Username	Problem	Language	Result	Execution time	Memory
5278		ainta	Sightseeing (NOI14_sightseeing)	C++98	25 / 25	2524 ms	127016 KiB

sightseeing

#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
#include<list>
using namespace std;
int n, m, E[5000010][2], TP[5000010][3], C[200100], par[500010], Res[500010], Q;
list<int>P[500010];
int find(int a){
	if (a == par[a])return a;
	return par[a] = find(par[a]);
}
int main()
{
	int i, j, x, y, k, pp;
	scanf("%d%d%d", &n, &m, &Q);
	for (i = 1; i <= n; i++){
		par[i] = i;
		P[i].push_back(i);
	}
	for (i = 0; i < m; i++){
		scanf("%d%d%d", &TP[i][0], &TP[i][1], &TP[i][2]);
		C[TP[i][2]]++;
	}
	for (i = 1; i <= 200001; i++)C[i] += C[i - 1];
	for (i = 0; i < m; i++){
		C[TP[i][2]]--;
		E[C[TP[i][2]]][0] = TP[i][0];
		E[C[TP[i][2]]][1] = TP[i][1];
	}
	for (i = 200000; i >= 0; i--){
		for (j = C[i]; j < C[i + 1]; j++){
			pp = find(1);
			x = find(E[j][0]), y = find(E[j][1]);
			if (x == y) continue;
			if (pp == y)swap(x, y);
			if (pp == x){
				for (list<int>::iterator it = P[y].begin(); it != P[y].end(); it++){
					Res[*it] = i;
				}
			}
			P[x].splice(P[x].begin(), P[y]);
			par[y] = x;
		}
	}
	while (Q--){
		scanf("%d", &i);
		printf("%d\n", Res[i]);
	}
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10