oj.uz

Submission #51229

# Submission time Handle Problem Language Result Execution time Memory
51229 2018-06-17T09:28:47 Z robert Sightseeing (NOI14_sightseeing) C++14
15 / 25
 3500 ms 110988 KB 
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> ii;

vector<vector<ii > > g;
ii UFDS[500100];
vector<int> d;
void dfs(int n, int p, int minv){
	d[n] = minv;
	for(int x=0; x<g[n].size(); x++){
		if(g[n][x].first!=p){
			dfs(g[n][x].first, n, 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);
	g.assign(N+1, vector<ii >());
	int a, b, c;
	priority_queue<pair<int, ii> > q;
	for(int m=0; m<M; m++){
		scanf("%d %d %d", &a, &b, &c);
		q.push({c, {a, b}});
	}
	for(int n=0; n<=N; n++)
		UFDS[n] = {n, 1};
	while(!q.empty()){
		pair<int, ii> t = q.top(); q.pop();
//		cout << t.first << endl;
		if(p(t.second.first)!=p(t.second.second)){
//			cout << "a" << endl;
			merge(t.second.first, t.second.second);
//			cout << t.second.first << " " << t.second.second << endl;
			g[t.second.first].push_back({t.second.second, t.first});
			g[t.second.second].push_back({t.second.first, t.first});
		}
//		cout << t.first << endl;
	}
	d.assign(N+1, 0);
	dfs(1, -1, 1e9);
	for(int q=0; q<Q; q++){
		int a;
		scanf("%d", &a);
		printf("%d\n", d[a]);
	}
	return 0;
}

Compilation message

sightseeing.cpp: In function 'void dfs(int, int, int)':
sightseeing.cpp:14: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:38:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
sightseeing.cpp: In function 'int main()':
sightseeing.cpp:43:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, M, Q; scanf("%d %d %d", &N, &M, &Q);
               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 3816 KB Output is correct
2 Correct 51 ms 3816 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3058 ms 63664 KB Output is correct
2 Execution timed out 3531 ms 110988 KB Time limit exceeded