Submission #265367

#	Time	Username	Problem	Language	Result	Execution time	Memory
265367		T0p_	Sightseeing (NOI14_sightseeing)	C++14	25 / 25	3028 ms	121752 KiB

sightseeing

#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 (stderr)

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