oj.uz

Submission #39369

# Submission time Handle Problem Language Result Execution time Memory
39369 2018-01-13T02:04:12 Z MatheusLealV Sightseeing (NOI14_sightseeing) C++14
15 / 25
 2399 ms 93428 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define N 500500
using namespace std;
typedef pair<int, int> pii;

int n, m, q, pai[N], peso[N], ans[N];

vector<pii> grafo[N];

vector< pair<int, pii> > A;

int Find(int x)
{
	if(x == pai[x]) return x;

	return pai[x] = Find(pai[x]);
}

void join(int a, int b)
{
	if(peso[a] >= peso[b]) swap(a, b);

	pai[a] = b;

	if(peso[a] == peso[b]) peso[b] ++;
}

void getans()
{
	memset(ans, 0x3f3f3f3f, sizeof ans);

	queue<pii> fila;

	fila.push(pii(1, 1));

	while(!fila.empty())
	{
		int x = fila.front().f, p = fila.front().s;

		fila.pop();

		for(auto v: grafo[x])
		{	
			if(v.f == p) continue;

			ans[v.f] = min(ans[x], v.s);

			fila.push(pii(v.f, x));
		}
	}
}

int main()
{
	//ios::sync_with_stdio(false); cin.tie(0);

	scanf("%d %d %d", &n, &m, &q);

	for(int i = 1, a, b, c; i <= m; i++)
	{
		scanf("%d %d %d", &a, &b, &c);

		A.push_back(make_pair(c, pii(a, b)));
	}

	sort(A.rbegin(), A.rend());

	for(int i = 1; i <= n; i++) pai[i] = i;

	for(auto p: A)
	{
		int a = Find(p.s.f), b = Find(p.s.s);

		if(a == b) continue;

		join(a, b);

		grafo[a].push_back(pii(b, p.f));

		grafo[b].push_back(pii(a, p.f));
	}

	getans();

	while(q--)
	{
		int x;

		scanf("%d", &x);;

		printf("%d\n", ans[x]);
	}
}

Compilation message

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:59:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &q);
                               ^
sightseeing.cpp:63:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &b, &c);
                                ^
sightseeing.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);;
                  ^

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19788 KB Output is correct
2 Correct 0 ms 19616 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 21968 KB Output is correct
2 Correct 43 ms 21812 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2399 ms 93428 KB Output is correct
2 Runtime error 0 ms 0 KB -1: Interrupted system call