Submission #122960

#	Time	Username	Problem	Language	Result	Execution time	Memory
122960		kimbj0709	Sightseeing (NOI14_sightseeing)	C++17	25 / 25	3131 ms	253868 KiB

sightseeing

#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);
  ufds[max(temp1,temp2)] = min(temp1,temp2);
  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 (stderr)

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

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