oj.uz

Submission #265367

# Submission time Handle Problem Language Result Execution time Memory
265367 2020-08-14T16:32:58 Z T0p_ Sightseeing (NOI14_sightseeing) C++14
25 / 25
 3028 ms 121752 KB 
#include<bits/stdc++.h>
using namespace std;

#define pb push_back

struct EDGE
{
	int u, v, w;
	bool operator < (const EDGE & o) const{
		return w > o.w;
	}
};

int pa[500500], ans[500500];
vector<EDGE> e;
vector<pair<int, int>> g[500500];

int fp(int u)
{
	return (u == pa[u]) ? u : pa[u] = fp(pa[u]);
}

void dfs(int u, int p, int v)
{
	ans[u] = v;
	for(auto x : g[u])
	{
		if(x.first == p) continue ;
		dfs(x.first, u, min(v, x.second));
	}
}

int main()
{
	int n, m, q;
	scanf(" %d %d %d",&n,&m,&q);
	for(int i=1 ; i<=n ; i++)
		pa[i] = i;
	while(m--)
	{
		int u, v, w;
		scanf(" %d %d %d",&u,&v,&w);
		e.pb({u, v, w});
	}
	sort(e.begin(), e.end());
	for(auto x : e)
	{
		int u = fp(x.u), v = fp(x.v);
		if(u != v)
		{
			pa[u] = v;
			g[x.u].pb({x.v, x.w});
			g[x.v].pb({x.u, x.w});
		}
	}
	dfs(1, 0, 1e9);
	while(q--)
	{
		int d;
		scanf(" %d",&d);
		printf("%d\n",ans[d]);
	}
	return 0;
}

Compilation message

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |  scanf(" %d %d %d",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |   scanf(" %d %d %d",&u,&v,&w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |   scanf(" %d",&d);
      |   ~~~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12032 KB Output is correct
2 Correct 9 ms 12032 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 9 ms 12160 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 14320 KB Output is correct
2 Correct 38 ms 14064 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2065 ms 65292 KB Output is correct
2 Correct 3028 ms 121752 KB Output is correct