oj.uz

Submission #39367

# Submission time Handle Problem Language Result Execution time Memory
39367 2018-01-13T01:47:32 Z MatheusLealV Sightseeing (NOI14_sightseeing) C++14
9 / 25
 1879 ms 171652 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define N 500010
#define logn 20
using namespace std;
typedef pair<int, int> pii;

int n, m, q, anc[N][logn], pai[N], peso[N], dist[N][logn], nivel[N];

vector<pii> grafo[N];

vector< pair<int, pii> > A;

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

		anc[v.f][0] = x;

		dist[v.f][0] = v.s;

		nivel[v.f] = nivel[x] + 1;

		dfs(v.f, x);
	}
}

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] ++;
}

inline int solve(int u, int v)
{
	if(nivel[u] < nivel[v]) swap(u, v);

	int resp = 2000000000;

	for(int i = logn - 1; i >= 0; i--)
		if(nivel[u] - (1<<i) >= nivel[v])
			resp = min(resp, dist[u][i]), u = anc[u][i];

	if(u == v) return resp;

	for(int i = logn - 1; i >= 0; i--)
		if(anc[u][i] != -1 && anc[u][i] != anc[v][i])
			resp = min(min(resp, dist[u][i]), dist[v][i]), u = anc[u][i], v = anc[v][i];

	return min(min(resp, dist[u][0]), dist[v][0]);
}

void init()
{
	memset(anc, -1, sizeof anc);

	memset(dist, 0x3f3f3f3f,sizeof dist);

	dfs(1, 1);

	for(int j = 1; j < logn; j++)
		for(int i = 1; i <= n; i++)
		{
			if(anc[i][j - 1] != -1) anc[i][j] = anc[ anc[i][j - 1] ][j - 1];

			if(anc[i][j - 1] != -1) dist[i][j] = min(dist[i][j - 1], dist[ anc[i][j - 1] ][j - 1]);
		}
}

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

	cin>>n>>m>>q;

	for(int i = 1, a, b, c; i <= m; i++)
	{
		cin>>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));
	}

	init();

	while(q--)
	{
		int x;

		cin>>x;

		cout<<solve(1, x)<<"\n";
	}
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 97884 KB Output is correct
2 Correct 9 ms 97884 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 100060 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1879 ms 171652 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -