oj.uz

Submission #51249

# Submission time Handle Problem Language Result Execution time Memory
51249 2018-06-17T10:10:28 Z robert Sightseeing (NOI14_sightseeing) C++14
25 / 25
 2876 ms 99032 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int, int> ii;

vector<vector<ii > > g;
ii UFDS[500100];
int d[500100];
void dfs(int n, int minv){
	d[n] = minv;
	for(int x=0; x<g[n].size(); x++){
		if(d[g[n][x].first]<0){
			dfs(g[n][x].first, min(minv, g[n][x].second));
		}
	}
}

int p(int n){
	if(n==UFDS[n].first)
		return n;
	return UFDS[n].first = p(UFDS[n].first);
}

int merge(int a, int b){
	a = p(a);
	b = p(b);
	if(UFDS[a].second<UFDS[b].second){
		UFDS[a].first = b;
	} else if(UFDS[a].second>UFDS[b].second){
		UFDS[b].first = a;
	} else {
		UFDS[a].first = b;
		UFDS[b].second++;
	}
}

int main(){
	iostream::sync_with_stdio(false);
	cin.tie(0);
	int N, M, Q; //scanf("%d %d %d", &N, &M, &Q);
	cin>>N>>M>>Q;
	g.assign(N+1, vector<ii >());
	int a, b, c;
	vector<pair<int, ii> > q(M);
	for(int m=0; m<M; m++){
//		scanf("%d %d %d", &a, &b, &c);
		cin>>q[m].second.first>>q[m].second.second>>q[m].first;
	}
	sort(q.begin(), q.end());
	for(int n=0; n<=N; n++)
		UFDS[n] = {n, 1};
	for(int m=M-1; m>=0; m--){
		pair<int, ii> t = q[m];
		if(p(t.second.first)!=p(t.second.second)){
			merge(t.second.first, t.second.second);
			g[t.second.first].push_back({t.second.second, t.first});
			g[t.second.second].push_back({t.second.first, t.first});
		}
	}
	memset(d, -1, sizeof(d));
	dfs(1, 1e9);
	for(int q=0; q<Q; q++){
		int a;
	//	scanf("%d", &a);
		cin>>a;
		cout << d[a] << "\n";
	}
	cout << flush;
	return 0;
}

Compilation message

sightseeing.cpp: In function 'void dfs(int, int)':
sightseeing.cpp:16:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int x=0; x<g[n].size(); x++){
               ~^~~~~~~~~~~~
sightseeing.cpp: In function 'int merge(int, int)':
sightseeing.cpp:40:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
sightseeing.cpp: In function 'int main()':
sightseeing.cpp:48:6: warning: unused variable 'a' [-Wunused-variable]
  int a, b, c;
      ^
sightseeing.cpp:48:9: warning: unused variable 'b' [-Wunused-variable]
  int a, b, c;
         ^
sightseeing.cpp:48:12: warning: unused variable 'c' [-Wunused-variable]
  int a, b, c;
            ^

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2488 KB Output is correct
2 Correct 5 ms 2532 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5592 KB Output is correct
2 Correct 32 ms 5592 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1935 ms 64140 KB Output is correct
2 Correct 2876 ms 99032 KB Output is correct