oj.uz

답안 #409150

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409150 2021-05-20T09:25:14 Z avaneeshk098 관광 (NOI14_sightseeing) C++17
25 / 25
 2905 ms 262144 KB 
#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.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 27724 KB Output is correct
2 Correct 17 ms 27736 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 27844 KB Output is correct
2 Correct 17 ms 27748 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 31628 KB Output is correct
2 Correct 45 ms 31032 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1969 ms 177008 KB Output is correct
2 Correct 2905 ms 262144 KB Output is correct