oj.uz

Submission #5278

# Submission time Handle Problem Language Result Execution time Memory
5278 2014-03-15T11:11:59 Z ainta Sightseeing (NOI14_sightseeing) C++
25 / 25
 2524 ms 127016 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 111364 KB Output is correct
2 Correct 4 ms 111364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 111364 KB Output is correct
2 Correct 8 ms 111364 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 112420 KB Output is correct
2 Correct 24 ms 112288 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1628 ms 122716 KB Output is correct
2 Correct 2524 ms 127016 KB Output is correct