Submission #682958

#	Time	Username	Problem	Language	Result	Execution time	Memory
682958		anonimy	Sightseeing (NOI14_sightseeing)	C++14	25 / 25	2104 ms	178480 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> par1, par2, sz, t;
vector<set<ll>> disjoint;

ll getpar(ll v, vector<ll>& par)
{
	if (par[v] == v) return v;
	return par[v] = getpar(par[v], par);
}

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

	if (v == u) return;

	bool join = false;
	if (getpar(1, par1) == getpar(v, par2))
		t[u] = w;
	else
		if (getpar(1, par1) == getpar(u, par2))
			t[v] = w;
		else
			join = true;

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

	par1[u] = v;
	sz[v] += sz[u];
	if (join)
		par2[u] = v;


}

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);
	t.resize(n + 1, 0);
	par1.resize(n + 1);
	par2.resize(n + 1);
	for (ll i = 1; i <= n; i++)
	{
		par1[i] = i;
		par2[i] = i;
	}

	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, w);
	}

	for (ll i = 0; i < q; i++)
	{
		ll x;
		cin >> x;
		cout << t[getpar(x, par2)] << "\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