Submission #124563

#	Time	Username	Problem	Language	Result	Execution time	Memory
124563		groeneprof	Sightseeing (NOI14_sightseeing)	C++14	25 / 25	3098 ms	262144 KiB

sightseeing

#include <bits/stdc++.h>
#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
// #define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 0;
struct edge
{
	int u, v, q;
	bool operator< (edge other){
		return mp(q, mp(u, v)) < mp(other.q, mp(other.u, other.v));
	}
};
int V, E, Q;
vector<edge> edgelist;
vector<vector<pair<int, int> > > graph;
vector<int> uf, dist;
int root(int a){
	if(uf[a] == a) return a;
	return uf[a] = root(uf[a]);
}
void merge(int a, int b){
	a = root(a); b = root(b);
	if(rand()%2) swap(a, b);
	uf[a] = b;
}

void dfs(int u, int par, int d){
	dist[u] = d;
	for(auto e : graph[u]) if(e.first!=par){
		dfs(e.first, u, min(d,e.second));
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>V>>E>>Q;
	edgelist.resize(E);
	uf.resize(V);
	graph.resize(V);
	dist.resize(V);
	F(i,E){
		int a, b, q;
		cin>>a>>b>>q;
		edgelist[i] = {a-1, b-1, q};
	}
	sort(edgelist.begin(), edgelist.end());
	F(i,V) uf[i] = i;
	for(int i = E-1; i>=0; i--){
		H(i);
		edge e = edgelist[i];
		if(root(e.u)!=root(e.v)){
			merge(e.u, e.v);
			graph[e.u].push_back({e.v, e.q});
			graph[e.v].push_back({e.u, e.q});
		}
	}
	dfs(0, -1, 1e18);
	F(i, Q){
		int a;
		cin>>a;
		cout<<dist[a-1]<<"\n";
	}
	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10