Submission #675478

#	Time	Username	Problem	Language	Result	Execution time	Memory
675478		QwertyPi	Sightseeing (NOI14_sightseeing)	C++14	25 / 25	3044 ms	262144 KiB

sightseeing

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