Submission #873530

#	Time	Username	Problem	Language	Result	Execution time	Memory
873530		dsyz	Sightseeing (NOI14_sightseeing)	C++17	25 / 25	1773 ms	262144 KiB

sightseeing

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (500005)
ll V,E,Q;
ll parent[MAXN];
ll dist[MAXN];
int visited[MAXN];
vector<pair<ll,pair<ll,ll>>> v;
vector<pair<ll,pair<ll,ll>>> A;
vector<pair<ll,ll>> NODE[MAXN];
long long find_set(ll x){
  if(parent[x] == x) return x;
  parent[x] = find_set(parent[x]);
  return parent[x];
}
void dfs(ll x){
  visited[x] = 1;
  for(auto u : NODE[x]){
    if(visited[u.second] == 0){
      if(dist[x] == 0){
        if(dist[u.second] == 0 || dist[u.second] > u.first){
          dist[u.second] = u.first;
          visited[u.second] = 1;
          dfs(u.second);
        }
      }else{
        if(dist[u.second] == 0 || (dist[u.second] < dist[x]) || dist[u.second] < u.first){
          dist[u.second] = min(dist[x],u.first);
          visited[u.second] = 1;
          dfs(u.second);
        }
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);cin.tie(0);
  cin>>V>>E>>Q;
  for(ll i = 0;i < E;i++){
    ll a,b,c;
    cin>>a>>b>>c;
    v.push_back(make_pair(c,make_pair(a - 1,b - 1)));
  }
  for(ll i = 0;i < V;i++){
    parent[i] = i;
  }
  sort(v.begin(),v.end(),greater<pair<ll,pair<ll,ll>>>());
  for(auto u : v){
    ll a = u.second.first;
    ll b = u.second.second;
    if(find_set(a) == find_set(b)){
      continue;
    }
    parent[find_set(a)] = find_set(b);
    A.push_back(u);
  }
  for(ll i = 0;i < A.size();i++){
    NODE[A[i].second.first].push_back(make_pair(A[i].first,A[i].second.second));
    NODE[A[i].second.second].push_back(make_pair(A[i].first,A[i].second.first));
  }
  dist[0] = 0;
  visited[0] = 1;
  dfs(0);
  for(ll i = 0;i < Q;i++){
    ll a;
    cin>>a;
    cout<<dist[a - 1]<<'\n';
  }
}

Compilation message (stderr)

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:58:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(ll i = 0;i < A.size();i++){
      |                ~~^~~~~~~~~~

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