oj.uz

Submission #682956

# Submission time Handle Problem Language Result Execution time Memory
682956 2023-01-17T11:18:46 Z anonimy Sightseeing (NOI14_sightseeing) C++14
25 / 25
 2458 ms 262144 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> ppll;

vector<ll> par, sz;
vector<set<ll>> disjoint;

ll getpar(ll v)
{
	if (par[v] == v) return v;
	return par[v] = getpar(par[v]);
}

void unit(ll v, ll u)
{
	v = getpar(v), u = getpar(u);

	if (v == u) return;
	if (sz[u] > sz[v]) swap(u, v);

	par[u] = v;
	sz[v] += sz[u];

	if (disjoint[u].size() > disjoint[v].size()) swap(disjoint[u], disjoint[v]);
	for (auto it = disjoint[u].begin(); it != disjoint[u].end(); it++)
		disjoint[v].insert((*it));
}

bool comp(ppll val1, ppll val2)
{
	return val1.first > val2.first;
}

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

	ll n, m, q;
	cin >> n >> m >> q;

	vector<ppll> edges(m);
	for (ll i = 0; i < m; i++)
	{
		ll a, b, w;
		cin >> a >> b >> w;

		edges[i] = { w, {a, b,} };
	}
		
	sort(edges.begin(), edges.end(), comp);

	sz.resize(n + 1, 1);
	par.resize(n + 1);
	disjoint.resize(n + 1);
	for (ll i = 1; i <= n; i++)
	{
		par[i] = i;
		if (i != 1)
			disjoint[i].insert(i);
	}


	vector<ll> ans(n+1);
	for (ll i = 0; i < m; i++)
	{
		ll a = edges[i].second.first, b = edges[i].second.second, w = edges[i].first;

		unit(a, b);
		if (getpar(1) == getpar(a))
		{
			ll p = getpar(a);
			while (!disjoint[p].empty())
			{
				ans[(*disjoint[p].begin())] = w;
				disjoint[p].erase(disjoint[p].begin());
			}
		}
	}

	for (ll i = 0; i < q; i++)
	{
		ll x;
		cin >> x;
		cout << ans[x] << "\n";
	}
}
/*
4 4 2
1 2 10
1 3 30
2 4 20
3 4 5
3
4
*/

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 8340 KB Output is correct
2 Correct 28 ms 7048 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1628 ms 190224 KB Output is correct
2 Correct 2458 ms 262144 KB Output is correct