Submission #522642

#TimeUsernameProblemLanguageResultExecution timeMemory
522642Andy__Andy__Sightseeing (NOI14_sightseeing)C++17
25 / 25
2848 ms262144 KiB
#include <bits/stdc++.h> #define ll long long #define int ll using namespace std; ifstream f ("test.in"); ofstream g ("test.out"); int teste=1; int n,m,q; int dp[500005]; int tata[500005]; int rang[500005]; vector < array < int ,2 > > G[500005]; int rep(int nod) { if(tata[nod] == nod) return nod; return (tata[nod] = rep(tata[nod])); } void comb(int i,int j,int cost) { int ri = rep(i); int rj = rep(j); if(ri != rj) { if(rang[ri]<rang[rj]) swap(ri,rj); tata[rj] = ri; rang[ri] += rang[rj]; G[i].push_back({cost,j}); G[j].push_back({cost,i}); } } vector < array < int ,3 > > E; void dfs(int nod,int tata) { for(auto x:G[nod]) { int vecin = x[1]; int cost = x[0]; if(vecin==tata) continue; dp[vecin] = min(dp[nod],cost); dfs(vecin,nod); } } void solve() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>q; for(int i=1;i<=n;++i) { tata[i]=i; } for(int i=1;i<=m;++i) { int a,b,c; cin>>a>>b>>c; E.push_back({-c,a,b}); } sort(E.begin(),E.end()); for(int i=0;i<E.size();++i) { comb(E[i][1],E[i][2],-E[i][0]); } dp[1] = 1e9; dfs(1,-1); for(;q--;) { int x; cin>>x; cout<<dp[x]<< '\n'; } } main() { while(teste--) { solve(); } return 0; }

Compilation message (stderr)

sightseeing.cpp: In function 'void solve()':
sightseeing.cpp:73:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i=0;i<E.size();++i)
      |                 ~^~~~~~~~~
sightseeing.cpp: At global scope:
sightseeing.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main()
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...