oj.uz

Submission #51242

# Submission time Handle Problem Language Result Execution time Memory
51242 2018-06-17T10:03:03 Z robert Sightseeing (NOI14_sightseeing) C++14
15 / 25
 3500 ms 64108 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

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;
	priority_queue<pair<int, ii> > q;
	for(int m=0; m<M; m++){
//		scanf("%d %d %d", &a, &b, &c);
		cin>>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();
		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] << endl;
	}
	return 0;
}

Compilation message

sightseeing.cpp: In function 'void dfs(int, int)':
sightseeing.cpp:15: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:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 5496 KB Output is correct
2 Correct 47 ms 5496 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3541 ms 64108 KB Time limit exceeded
2 Halted 0 ms 0 KB -