Submission #39365

#TimeUsernameProblemLanguageResultExecution timeMemory
39365wzySightseeing (NOI14_sightseeing)C++11
15 / 25
2049 ms114532 KiB
#include <bits/stdc++.h> using namespace std; #define F first #define S second #define pii pair<int,int> #define int long long #define ieps 500500 #define find alice #define join wonderland #define eps (int) 1e9 #define mp make_pair #define pb push_back inline int read_int() { register char c=0; int a=0; while (c<33) c=getchar(); while (c>33) { a=a*10+c-'0', c=getchar(); } return a; } int pai[ieps] , n , m , q , peso[ieps] , custo[ieps]; int find(int x){ return pai[x] == x ? x : pai[x] = find(pai[x]); } void join(int u , int v){ u = find(u) , v = find(v); if(peso[u] > peso[v]) swap(u, v); pai[u] = v , peso[v] += peso[u]; } struct edges{ int x, y , z; }; vector<pii> adj[ieps]; bool cmp(edges a , edges b){ return a.z > b.z; } void dfs(int x , int y){ for(auto t : adj[x]){ if(t.F == y) continue; custo[t.F] = min(t.S , custo[x]); dfs(t.F, x); } } int32_t main(){ n = read_int() , m = read_int() , q = read_int(); vector<edges> v(m); for(int i = 0 ; i < n; i++){ pai[i] = i , peso[i] = 0; } for(int i = 0 ; i < m ; i++){ v[i].x = read_int() , v[i].y = read_int() , v[i].z = read_int(); v[i].x -- , v[i].y--; } sort(v.begin() , v.end() , cmp); for(int i = 0 ; i < m; i++){ if(find(v[i].x) != find(v[i].y)){ join(v[i].x , v[i].y); adj[v[i].x].pb(pii(v[i].y , v[i].z)); adj[v[i].y].pb(pii(v[i].x , v[i].z)); } } for(int i = 0 ; i < ieps; i++) custo[i] = eps; dfs(0 , 0); while(q--){ int x; x = read_int(); printf("%lld\n" , custo[x-1]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...