Submission #409150

#	Time	Username	Problem	Language	Result	Execution time	Memory
409150		avaneeshk098	Sightseeing (NOI14_sightseeing)	C++17	25 / 25	2905 ms	262144 KiB

sightseeing

#include <bits/stdc++.h>
//#include "/Users/avaneeshk098/stdc++.h"

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define mt              make_tuple
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define max_size        100000000
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define mod             13371337
#define w(t)			int t; cin >> t; while(t--)
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define range(a,b)      substr(a,b-a+1)
#define mina(a,b,c)		min(a, min(b, c))
#define maxa(a,b,c)		max(a, max(b, c))
#define endl 			'\n'
#define trace(x)        cerr<<#x<<": "<<x<<" "<<endl;
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define FOR(x,y)		for(int i = x; i < y; i++)

using namespace std;

bool sortbyfirst(const pair<int,pii> &a, const pair<int,pii> &b){ return (a.first > b.first); } 

int64_t ceil_div(int64_t a, int64_t b) {if(a%b != 0){ return ((a/b)+1);} else{ return (a/b);}}

double max(double a, double b){ if(a >= b){ return a; } else{ return b; } }

double min(double a, double b){if(a <= b){return a;} else{return b;}}

bool modd(double a, double b){if(floor(a/b) == ceil(a/b)){return true;} return false;}

bool stringsort(const string &a, const string &b){return a.length() > b.length();}

const int MN = 5e5 + 5;
vi link(MN);
vi siz(MN);
int find(int x){
	if(x == link[x]) return x;
	return link[x] = find(link[x]);
}

bool same(int a, int b){
	return find(a) == find(b);
}

void unite(int a,int b){
	a = find(a);
	b = find(b);
	if(siz[a] < siz[b]) swap(a,b);
	siz[a] += siz[b];
	link[b] = a;
}

vector<vector<pii>> adj(MN);
vi ans(MN);
vi visited(MN);

void dfs(int s, int t, int w){
	if(visited[s]) return;
	visited[s] = 1;
	if(t != -1){
		ans[s] = min(w, ans[t]);
	}
	for(auto i : adj[s]){
		dfs(i.first, s, i.second);
	}
}

void solve() {
	int n,m,r;
	cin >> n >> m >> r;
	vector<pair<int, pii>> edg;
	for(int i = 1;i <= n; i++){
		ans[i] = inf;
		visited[i] = 0;
	}
	for(int i = 0; i < m; i++){
		int u,v,w;
		cin >> u >> v >> w;
		edg.pb({w,{u,v}});	
	}
	for(int i = 1; i <= n; i++){ link[i] = i; siz[i] = 1;}
	sort(edg.begin(), edg.end(), sortbyfirst);
	for(auto e : edg){
		int w = e.first, u = e.second.first, v = e.second.second;
		if(!same(u,v)){ 
			unite(u,v);
			adj[u].pb({v,w});
			adj[v].pb({u,w});
		}
	}
	dfs(1,-1,0);
	for(int i = 1; i <= r; i++){
		int l;
		cin >> l;
		cout << ans[l] << endl;
	}
	
}


int32_t main(){
	FIO;
	solve();
    return 0;
}

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