oj.uz

Submission #682958

# Submission time Handle Problem Language Result Execution time Memory
682958 2023-01-17T11:26:31 Z anonimy Sightseeing (NOI14_sightseeing) C++14
25 / 25
 2104 ms 178480 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> 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.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 464 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 23 ms 3084 KB Output is correct
2 Correct 19 ms 2836 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1274 ms 84000 KB Output is correct
2 Correct 2104 ms 178480 KB Output is correct