oj.uz

Submission #170400

# Submission time Handle Problem Language Result Execution time Memory
170400 2019-12-25T04:07:11 Z banterbry Sightseeing (NOI14_sightseeing) C++17
25 / 25
 3122 ms 122136 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12144 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12152 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 15224 KB Output is correct
2 Correct 45 ms 14840 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2103 ms 68336 KB Output is correct
2 Correct 3122 ms 122136 KB Output is correct