Submission #51246

#	Time	Username	Problem	Language	Result	Execution time	Memory
51246		robert	Sightseeing (NOI14_sightseeing)	C++14	15 / 25	3551 ms	110980 KiB

sightseeing

#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] << "\n";
	}
	cout << flush;
	return 0;
}

Compilation message (stderr)

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 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 0 / 10