oj.uz

Submission #873530

# Submission time Handle Problem Language Result Execution time Memory
873530 2023-11-15T09:04:55 Z dsyz Sightseeing (NOI14_sightseeing) C++17
25 / 25
 1773 ms 262144 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17244 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 21824 KB Output is correct
2 Correct 22 ms 21072 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1169 ms 180756 KB Output is correct
2 Correct 1773 ms 262144 KB Output is correct