oj.uz

Submission #675478

# Submission time Handle Problem Language Result Execution time Memory
675478 2022-12-27T10:29:33 Z QwertyPi Sightseeing (NOI14_sightseeing) C++14
25 / 25
 3044 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

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

struct qry{
	int x, i;
	bool operator< (const qry& o) {
		return x < o.x;
	}
};

const int MAXN = 5e5 + 11;
int ans[MAXN];
struct DSU{
	int dsu[MAXN]; vector<int> sons[MAXN];
	void init(int n){
		for(int i = 1; i <= n; i++) dsu[i] = i, sons[i].push_back(i);
	}
	int f(int x){
		return x == dsu[x] ? x : dsu[x] = f(dsu[x]);
	}
	void g(int x, int y, int w){
		x = f(x), y = f(y);
		if(x == y) return;
		if(f(1) == f(y)) swap(x, y);
		if(f(1) == f(x)){
			for(auto i : sons[y]){
				ans[i] = w;
			}
		}else{
			if(sons[x].size() < sons[y].size()) swap(x, y);
			for(auto i : sons[y]){
				sons[x].push_back(i);
			}
		}
		sons[y].clear();
		dsu[y] = x;
	}
} dsu;

vector<edge> G[MAXN];
vector<int> dq[MAXN];
int main(){
	cin.tie(0); cout.tie(0)->sync_with_stdio(false);
	int n, m, q; cin >> n >> m >> q;
	for(int i = 0; i < m; i++){
		int u, v, w; cin >> u >> v >> w;
		G[u].push_back({u, v, w});
		G[v].push_back({v, u, w});
	}
	dq[MAXN - 1].push_back(1); ans[1] = MAXN - 1;
	for(int d = MAXN - 1; d >= 0; d--){
		while(dq[d].size()){
			int t = dq[d].back(); dq[d].pop_back();
			if(ans[t] > d) continue;
			for(auto e : G[t]){
				int nd = min(d, e.w);
				if(nd > ans[e.v]){
					ans[e.v] = nd;
					dq[nd].push_back(e.v);
				}
			}
		}
	}
	for(int i = 0; i < q; i++){
		int x; cin >> x; cout << ans[x] << '\n';
	}
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35540 KB Output is correct
2 Correct 17 ms 35540 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35668 KB Output is correct
2 Correct 18 ms 35584 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 38356 KB Output is correct
2 Correct 37 ms 37644 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2011 ms 162404 KB Output is correct
2 Correct 3044 ms 262144 KB Output is correct