제출 #828605

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
828605		NK_	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	44 ms	13772 KiB

roadsideadverts

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using vi = V<int>;
using ll = long long;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;

const int LG = 16;

int main() {
	cin.tie(0)->sync_with_stdio(0);
 	
	int N; cin >> N;

	V<vpi> adj(N); for(int i = 0; i < N - 1; i++) {
		int u, v, w; cin >> u >> v >> w;
		adj[u].pb(mp(v, w));
		adj[v].pb(mp(u, w));
	}

	vi st(N), en(N), dep(N);
	V<vi> up(N, vi(LG));

	int t = 0;
	function<void(int, int)> gen = [&](int u, int p) {
		up[u][0] = p;
		for(int i = 1; i < LG; i++) up[u][i] = up[up[u][i-1]][i-1];

		st[u] = t++;
		for(auto& e : adj[u]) if (e.f != p) {
			dep[e.f] = dep[u] + e.s; gen(e.f, u);
		}
		en[u] = t - 1;
	};
	
	dep[0] = 0; gen(0, 0);

	auto anc = [&](int a, int b) { return st[a] <= st[b] && en[b] <= en[a]; };

	auto lca = [&](int a, int b) {
		if (anc(a, b)) return a;
		// if (anc(b, a)) return b;

		for(int i = LG - 1; i >= 0; i--) {
			if (!anc(up[a][i], b)) a = up[a][i];
		}

		return up[a][0];
	};

	auto dist = [&](int u, int v) {
		// cout << u << " - " << v << " - " << lca(u, v) << endl;
		return dep[u] + dep[v] - 2 * dep[lca(u, v)];
	};


	int Q; cin >> Q;
	for(int i = 0; i < Q; i++) { 
		vi A(5); for(auto& x : A) cin >> x;

		sort(begin(A), end(A), [&](int x, int y) { return st[x] < st[y]; });

		for(int x = 0; x < 4; x++) A.pb(lca(A[x], A[x+1]));

		sort(begin(A), end(A), [&](int x, int y) { return st[x] < st[y]; });
		A.erase(unique(begin(A), end(A)), end(A));

		vi stk = {-1}; int ans = 0;
		for(auto& x : A) {
			while(stk.back() != -1 && en[stk.back()] < st[x]) stk.pop_back();

			// for(auto& y : stk) cout << y << ", ";
			// cout << endl;

			if (stk.back() != -1) ans += dist(stk.back(), x);
			stk.pb(x);
		}
		// cout << endl;

		cout << ans << nl;
	}

	exit(0-0);
}					

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30