Submission #124603

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
124603	2019-07-03T14:53:26 Z	MoNsTeR_CuBe	Sightseeing (NOI14_sightseeing)	C++17	15 / 25	3500 ms	99544 KB

sightseeing

#include <bits/stdc++.h>
using namespace std;

const int INF = numeric_limits<int>::max();

vector< int > dist;

vector< int > U;

vector< int > taille;

int getParents(int a){
	if(U[a] == a) return a;
	else return U[a] = getParents(U[a]);
}

void Union(int a, int b){
	a = getParents(a);
	b = getParents(b);
	
	if(taille[a] < taille[b]){
		taille[a] += taille[b];
		U[a] = U[b];
	}else{
		taille[b] += taille[a];
		U[b] = U[a];
	}
}

vector< vector< pair<int, int> > > Graph;

vector< bool > visited;

void dfs(int node, int cost){
	dist[node] = cost;
	visited[node] = true;
	for(pair<int, int> p : Graph[node]){
		if(visited[p.first]) continue;
		dfs(p.first, min(cost, p.second));
	}
}

signed main(){
	
	int n, m, q;
	scanf("%lld%lld%lld", &n, &m, &q);
	
	Graph.resize(n+1);
	
	vector< tuple<int, int, int> > edges(m);
	
	for(int i = 0; i < m; i++){
		
		int a, b, c;
		scanf("%lld%lld%lld", &a, &b, &c);
		
		edges[i] = make_tuple(c,a,b);
	}
	
	taille.assign(n+1,1);
	dist.resize(n+1);
	U.resize(n+1);
	
	for(int i = 0; i <= n; i++){
		U[i] = i;
	}
	
	sort(edges.begin(), edges.end(), greater< tuple<int, int, int> >());
	
	for(int i = 0; i < m; i++){
		int a = get<1>(edges[i]);
		int b = get<2>(edges[i]);
		
		int c = get<0>(edges[i]);
		
		if(getParents(a) == getParents(b)){
			continue;
		}
		Union(a,b);
		
		Graph[a].push_back(make_pair(b,c));
		Graph[b].push_back(make_pair(a,c));
	}
	visited.assign(n+1, false);
	dfs(1,INF);
	
	for(int i = 0; i < q; i++){
		int a;
		cin >> a;
		printf("%lld\n", dist[a]);
	}
}

Compilation message

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:46:34: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
  scanf("%lld%lld%lld", &n, &m, &q);
                        ~~        ^
sightseeing.cpp:46:34: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'int*' [-Wformat=]
sightseeing.cpp:46:34: warning: format '%lld' expects argument of type 'long long int*', but argument 4 has type 'int*' [-Wformat=]
sightseeing.cpp:55:35: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
   scanf("%lld%lld%lld", &a, &b, &c);
                         ~~        ^
sightseeing.cpp:55:35: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'int*' [-Wformat=]
sightseeing.cpp:55:35: warning: format '%lld' expects argument of type 'long long int*', but argument 4 has type 'int*' [-Wformat=]
sightseeing.cpp:90:27: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' [-Wformat=]
   printf("%lld\n", dist[a]);
                           ^
sightseeing.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 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	4 ms	504 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct

Subtask #3

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	3832 KB	Output is correct
2	Correct	52 ms	3576 KB	Output is correct

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2967 ms	63880 KB	Output is correct
2	Execution timed out	3554 ms	99544 KB	Time limit exceeded