Submission #682956

#	Time	Username	Problem	Language	Result	Execution time	Memory
682956		anonimy	Sightseeing (NOI14_sightseeing)	C++14	25 / 25	2458 ms	262144 KiB

sightseeing

#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 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10