Submission #170400

#	Time	Username	Problem	Language	Result	Execution time	Memory
170400		banterbry	Sightseeing (NOI14_sightseeing)	C++17	25 / 25	3122 ms	122136 KiB

sightseeing

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
typedef pair<int,int> pi;

const int MAXE = 5000005, MAXN = 500005;
int N,E,Q,p[MAXN],ans[MAXN];
vector<pi> adj[MAXN];
struct edge {
	int u,v,c;
} edgelist[MAXE];

bool cmp(edge a, edge b) {return a.c > b.c;}

struct ufds_ {
	ufds_() {
		for (int i = 1; i <= N; i++) p[i] = i;
	}
	int find(int x) {
		if (p[x] == x) return x;
		return p[x] = find(p[x]);
	}
	void merge(int x, int y) {
		x = find(x); y = find(y);
		p[x] = y;
	}
} ufds;

void dfs(int x, int par, int w) {
	ans[x] = w;
	for (auto it: adj[x]) {
		if (it.first == par) continue;
		dfs(it.first,x,min(w,it.second));
	}
}

int main() {
	scanf("%d%d%d",&N,&E,&Q);
	for (int i = 0; i < E; i++) {
		scanf("%d%d%d",&edgelist[i].u,&edgelist[i].v,&edgelist[i].c);
	}
	sort(edgelist,edgelist+E,cmp);
	ufds_();
	for (int i = 0; i < E; i++) {
		int u = edgelist[i].u, v = edgelist[i].v, c = edgelist[i].c;
		if (ufds.find(u) == ufds.find(v)) continue;
		ufds.merge(u,v);
		adj[u].pb(mp(v,c));
		adj[v].pb(mp(u,c));
	}
	dfs(1,-1,1e9+7);
	while (Q--) {
		int x; scanf("%d",&x);
		printf("%d\n",ans[x]);
	}
	return 0;
}

Compilation message (stderr)

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&N,&E,&Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~
sightseeing.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&edgelist[i].u,&edgelist[i].v,&edgelist[i].c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:55:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d",&x);
          ~~~~~^~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10