Submission #492618

#TimeUsernameProblemLanguageResultExecution timeMemory
492618BiazSightseeing (NOI14_sightseeing)C++17
15 / 25
3571 ms64480 KiB
#include <bits/stdc++.h> //#define int long long //#define double long double #define Nanase_Kurumi_aka_menhera_chan_is_mine ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define pb push_back #define pi pair<int, int> #define ALL(i) i.begin(),i.end() #define gcd(i,j) __gcd(i,j) #define fi first #define se second #define eps 0.00000001 #define ist insert #define DNE nullptr //#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") //#pragma GCC optimize("O2") int max(int x,int y){return x>=y?x:y;} int min(int x,int y){return x>=y?y:x;} using namespace std; typedef int ll; const int N=500005; const int M=5000005; const int MOD=1000000007;//998244353; //const int INF=1000000000000000000;//2147483647; int n,m,Q; struct I{ int a,b,c; bool operator<(I const& rh)const{ return c>rh.c; } }e[M]; int p[N]; int res[N]; vector<int> gr[N]; int boss(int a){return a==p[a]?a:p[a]=boss(p[a]);} void merge(int a,int b){ if (gr[a].size()<gr[b].size()){ p[a]=b; for (int &i:gr[a]) gr[b].pb(i); gr[a].clear(); } else{ p[b]=a; for (int &i:gr[b]) gr[a].pb(i); gr[b].clear(); } } inline void sol(){ cin >>n>>m>>Q; for (int i=0;i<m;i++) cin >>e[i].a>>e[i].b>>e[i].c; sort(e,e+m); for (int i=1;i<=n;i++) p[i]=i,gr[i].pb(i); for (int i=0;i<m;i++){ int x=boss(e[i].a),y=boss(e[i].b); if (x==y) continue; merge(x,y); if (boss(x)==boss(1)){ for (int &v:gr[x]) if (res[v]==0) res[v]=e[i].c; } if (boss(y)==boss(1)){ for (int &v:gr[y]) if (res[v]==0) res[v]=e[i].c; } } for (int i=0,t;i<Q;i++){ cin >>t; cout <<res[t]<<'\n'; } } signed main(){ Nanase_Kurumi_aka_menhera_chan_is_mine int _=1; //cin >>_; while (_--) sol(); return 0; } /* 4 4 2 1 2 10 1 3 30 2 4 20 3 4 5 3 4*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...