Submission #1147513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147513		KK_1729	Roadside Advertisements (NOI17_roadsideadverts)	C++20	100 / 100	116 ms	17776 KiB

roadsideadverts

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
	for (auto x: a) cout << x << " ";
	cout << endl;
}
vector<vector<pair<int, int>>> graph;vector<vector<int>> t;
vector<int> tin; int ans = 0;
vector<vector<int>> up;
int timer = 0; vector<int> imp;
vector<int> depth;vector<int> orz;


void dfs(int x, int p = -1){


	tin[x] = ++timer;
	for (auto [item, w]: graph[x]){

		if (item == p) continue;
		up[item][0] = x;
		depth[item] = depth[x]+1;
		orz[item] = orz[x]+w;
		dfs(item, x);
		
	}
}
int jump(int x, int k){
	if (k <= 0) return x;
	for (int i = 0; i < 17; i++){
		if (k&(1 << i)) x = up[x][i];
	}
	return x;
}

int lca(int x, int y){
	if (depth[x] < depth[y]) swap(x, y);
	x = jump(x, depth[x]-depth[y]);
	if (x == y) return x;

	for (int i = 16; i >= 0; i--){
		if (up[x][i] != up[y][i]){
			x = up[x][i];
			y = up[y][i];
		}
	}
	return up[x][0];
}

bool isanc(int x, int y){
	return lca(x, y) == x;
}
vector<int> buildtree(vector<int> v){
	sort(v.begin(), v.end(), [](int x, int y){
		return tin[x] < tin[y];
	});

	int s = v.size();
	for (int i = 0; i < s-1; i++){
		int lc = lca(v[i], v[i+1]);
		v.push_back(lc);
	}
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	sort(all(v), [](int x, int y){
		return tin[x] < tin[y];
	});

	stack<int> st;
	st.push(v[0]);

	for (int i = 1; i < v.size(); ++i){
		assert(st.size());
		while (!isanc(st.top(), v[i])) st.pop();
		t[st.top()].push_back(v[i]);
		st.push(v[i]);
	}
	return v;
}
void solve(){
	int n; cin >> n;
	graph.resize(n+1);
	up.resize(n+1, vector<int>(17));
	depth.resize(n+1);
	tin.resize(n+1);
	t.resize(n+100);
	// imp.resize(n+1);
	orz.resize(n+1);
	FOR(i,0,n-1){
		int u, v, w; cin >> u >> v >> w;

		graph[u].pb({v, w});
		graph[v].pb({u, w});
	}
	dfs(0);
	up[0][0] = 1;
	for (int k = 1; k <= 16; k++){
		for (int i = 0; i < n; i++) up[i][k] = up[ up[i][k-1] ][k-1];
	}

	int q; cin >> q;
	while (q--){
		vector<int> v(5);
		FOR(i,0,5){
			cin >> v[i];
		}
		
		vector<int> nodes = buildtree(v);
		int ans = 0;
		for (auto x: nodes){
			for (auto item: t[x]) ans += orz[item]-orz[x];
		}
		cout << ans << endl;
		for (auto x: nodes){
			t[x].clear();
		}
	}


}


int32_t main(){
	ios::sync_with_stdio(false);
	int t = 1; // cin >> t;
	while (t--) solve();
}

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