Submission #674916

#	Time	Username	Problem	Language	Result	Execution time	Memory
674916		QwertyPi	Roadside Advertisements (NOI17_roadsideadverts)	C++14	7 / 100	97 ms	11216 KiB

roadsideadverts

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;

const int MAXN = 5e4 + 11;
vector<pii> G[MAXN];
int tin[MAXN], tout[MAXN], timer;
int p[MAXN], d[MAXN], w[MAXN], anc[MAXN][20], dep[MAXN];
void dfs_prec(int v, int pa = -1){
	tin[v] = ++timer;
	for(auto i : G[v]){
		int u = i.fi, _w = i.se;
		if(u != pa){
			w[u] = _w; d[u] = d[v] + w[u]; dep[u] = dep[v] + 1; anc[u][0] = p[u] = v;
			for(int j = 1; j < 20; j++) anc[u][j] = anc[anc[u][j - 1]][j - 1];
			dfs_prec(u, v);
		}
	}
	tout[v] = timer;
}

int kth_anc(int u, int k){
	for(int j = 19; j >= 0; j--){
		if(k >= (1 << j)) u = anc[u][j], k -= (1 << j);
	}
	return u;
}

int lca(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	u = kth_anc(u, dep[u] - dep[v]);
	for(int j = 19; j >= 0; j--){
		if(anc[u][j] != anc[v][j]){
			u = anc[u][j], v = anc[v][j];
		}
	}
	return u == v ? u : p[u];
}

bool is_anc(int u, int v){
	return tin[u] <= tin[v] && tout[v] >= tout[u];
}

int32_t main(){
	int n; cin >> n;
	for(int i = 0; i < n - 1; i++){
		int u, v, w; cin >> u >> v >> w;
		G[u].push_back({v, w});
		G[v].push_back({u, w});
	}
	dfs_prec(0);
	int q; cin >> q;
	for(int i = 0; i < q; i++){
		vector<int> v;
		for(int j = 0; j < 5; j++){
			int val; cin >> val; v.push_back(val);
		}
		sort(v.begin(), v.end(), [](int a, int b){
			return tin[a] < tin[b];
		});
		vector<int> path; path.push_back(v[0]);
		int ans = 0;
		for(int i = 1; i < v.size(); i++){
			while(path.size() >= 2 && is_anc(lca(path.back(), v[i]), path[path.size() - 2])){
				ans += d[path.back()] - d[path[path.size() - 2]];
				path.pop_back();
			}
			if(is_anc(path.back(), v[i])){
				path.push_back(v[i]);
			}else{
				int l = lca(path.back(), v[i]);
				ans += d[path.back()] - d[l];
				path.pop_back();
				path.push_back(l);
				path.push_back(v[i]);
			}
		}
		while(path.size() >= 2){
			ans += d[path.back()] - d[path[path.size() - 2]];
			path.pop_back();
		}
		cout << ans << endl;
	}
}

Compilation message (stderr)

roadsideadverts.cpp: In function 'int32_t main()':
roadsideadverts.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i = 1; i < v.size(); i++){
      |                  ~~^~~~~~~~~~

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