oj.uz

Submission #124591

# Submission time Handle Problem Language Result Execution time Memory
124591 2019-07-03T14:43:01 Z streifi Sightseeing (NOI14_sightseeing) C++14
9 / 25
 3500 ms 60452 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

struct adj_edge {
	int v, w;
	bool operator<(const adj_edge &other) const {
		return w < other.w;
	}
};

struct list_edge {
	int u, v, w;
	bool operator<(const list_edge &other) const {
		return w < other.w;
	}
};

int V, E, Q;
vector< vector<adj_edge> > adj;
vector<list_edge> edge_list;
vector<int> par, vis;

int find(int u) {
	if (par[u] == u)
		return u;
	return par[u] = find(par[u]);
}

void merge(int u, int v) {
	int ru = find(u), rv = find(v);
	if (ru == rv)
		return;
	if (rand()%2)
		swap(ru, rv);
	par[ru] = rv;
}

void kruskall() {
	for (int i = 0; i < V; ++i)
		par.push_back(i);
	sort(edge_list.rbegin(), edge_list.rend());
	for (list_edge e: edge_list) {
		if (find(e.u) == find(e.v))
			continue;
		merge(e.u, e.v);
		adj[e.u].push_back({e.v, e.w});
		adj[e.v].push_back({e.u, e.w});
	}
}

int dfs(int cur, int dest) {
	if (vis[cur])
		return -1;
	vis[cur] = 1;
	if (cur == dest)
		return INF;
	for (adj_edge e: adj[cur]) {
		int res = dfs(e.v, dest);
		if (res != -1)
			return min(res, e.w);
	}
	return -1;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> V >> E >> Q;
	adj.resize(V);
	for (int e = 0; e < E; ++e) {
		int u, v, q;
		cin >> u >> v >> q;
		edge_list.push_back({u-1, v-1, q});
	}
	kruskall();
	for (int q = 0; q < Q; ++q) {
		int X;
		cin >> X;
		vis.assign(V, 0);
		cout << dfs(0, X-1) << endl;
	}
}

Subtask #1
4.0 / 4.0

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

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3539 ms 3676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3542 ms 60452 KB Time limit exceeded
2 Halted 0 ms 0 KB -