oj.uz

Submission #122959

# Submission time Handle Problem Language Result Execution time Memory
122959 2019-06-29T16:51:04 Z kimbj0709 Sightseeing (NOI14_sightseeing) C++17
25 / 25
 3170 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> ufds(500005);
vector<int> sum(500005,1);
int find(int k){
  if(k==ufds[k]){
    return k;
  }
  return ufds[k] = find(ufds[k]);
}
void merge(int a,int b){
  int temp1 = find(a);
  int temp2 = find(b);
  if(sum[temp1]>sum[temp2]){
    ufds[temp2] = ufds[temp1];
    sum[temp1] += sum[temp2];
  }
  else{
    ufds[temp1] = ufds[temp2];
    sum[temp2] += sum[temp1];
  }
  return;
}
void dfs(int node,int val,vector<vector<pair<int,int> > > &adj,vector<int> &visited,int parent){
  for(auto k:adj[node]){
    if(k.first==parent){
      continue;
    }
    if(visited[k.first]>min(val,k.second)){
      visited[k.first] = min(val,k.second);
      dfs(k.first,min(val,k.second),adj,visited,node);
    }
  }
  return;

}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  for(int i=0;i<ufds.size();i++){
    ufds[i] = i;
  }
  int no_of_vertex,no_of_edge,no_of_query;
  int input1,input2,input3;
  vector<pair<int,pair<int,int> > > vect1;
  cin >> no_of_vertex >> no_of_edge >> no_of_query;
  vector<vector<pair<int,int> > > adj(no_of_vertex+2);
  for(int i=0;i<no_of_edge;i++){
    cin >> input1 >> input2 >> input3;
    vect1.push_back({input3,{input1,input2}});
  }
  sort(vect1.begin(),vect1.end());
  reverse(vect1.begin(),vect1.end());
  for(int i=0;i<vect1.size();i++){
    if(find(vect1[i].second.first)!=find(vect1[i].second.second)){
      merge(vect1[i].second.first,vect1[i].second.second);
      adj[vect1[i].second.first].push_back({vect1[i].second.second,vect1[i].first});
      adj[vect1[i].second.second].push_back({vect1[i].second.first,vect1[i].first});
    }
  }
  vector<int> visited(no_of_vertex+2,INT_MAX);
  visited[1] = -1;
  dfs(1,INT_MAX,adj,visited,-1);
  for(int i=0;i<no_of_query;i++){
    cin >> input1;
    cout << visited[input1] << "\n";
  }


}

Compilation message

sightseeing.cpp: In function 'int32_t main()':
sightseeing.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<ufds.size();i++){
               ~^~~~~~~~~~~~
sightseeing.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<vect1.size();i++){
               ~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8316 KB Output is correct
2 Correct 8 ms 8184 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8568 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13292 KB Output is correct
2 Correct 43 ms 12628 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2033 ms 169000 KB Output is correct
2 Correct 3170 ms 262144 KB Output is correct