Submission #681857

#	Time	Username	Problem	Language	Result	Execution time	Memory
681857		dsyz	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	90 ms	28520 KiB

roadsideadverts

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (500005)
ll V;
vector<pair<ll,ll> > v[MAXN];
ll parent[20][MAXN];
ll depth[MAXN];
ll dist[MAXN];
ll visited[MAXN];
void distdfs(ll x){
	visited[x] = 1;
	for(auto u : v[x]){
		if(visited[u.first] == 0){
			dist[u.first] = dist[x] + u.second;
			visited[u.first] = 1;
			distdfs(u.first);
		}
	}
}
void dfs(ll x,ll nodeparent,ll nodedepth){
	parent[0][x] = nodeparent;
	depth[x] = nodedepth;
	for(ll i = 0;i < v[x].size();i++){
		if(v[x][i].first != nodeparent){
			dfs(v[x][i].first,x,nodedepth + 1);
		}
	}
}
void lcainit(){
	for(ll i = 1;i < 20;i++){
		for(ll j = 0;j < V;j++){
			parent[i][j] = parent[i - 1][parent[i - 1][j]];
		}
	}
}
long long lca(ll u,ll v){
	if(depth[u] > depth[v]){
			swap(u,v);
		}
	ll diff = depth[v] - depth[u];
	for(ll i = 0;i < 20;i++){
		if(diff & (1<<i)){
			v = parent[i][v];
		} 
	}
	if(u == v){
	   return u;
	} 
	for(ll i = 19;i >= 0;i--){
		if(parent[i][u] != parent[i][v]){
			u = parent[i][u];
			v = parent[i][v];
	    }
	}
	return parent[0][u];
}
ll pre[MAXN];
ll cnt = 0;
void order(ll x,ll p){
	pre[x] = cnt++;
	for(auto u : v[x]){
		if(u.first != p){
			order(u.first,x);
		}
	}
}
bool cmp(ll a,ll b){
	return pre[a] < pre[b];
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>V;
	for(ll i = 0;i < V - 1;i++){
		ll a,b,w;
		cin>>a>>b>>w;
		v[a].push_back(make_pair(b,w));
		v[b].push_back(make_pair(a,w));	  
	}
	dist[0] = 0;
	visited[0] = 1;
	distdfs(0);
	dfs(0,0,0);
	lcainit();
	order(0,-1);
	ll Q;
	cin>>Q;
	for(ll q = 0;q < Q;q++){
		ll arr[5];
		for(ll i = 0;i < 5;i++){
			cin>>arr[i];
		}
		sort(arr,arr + 5,cmp);
		ll leader = arr[0]; //lca of all 5 nodes
		for(ll i = 1;i < 5;i++){
			leader = lca(leader,arr[i]);	
		}
		ll sum = (dist[leader] + dist[arr[0]] - 2 * dist[leader]);
		for(ll i = 1;i < 5;i++){
			ll a = lca(arr[i - 1],arr[i]);
			ll b = arr[i];
			sum += (dist[a] + dist[b] - 2 * dist[a]);
		}
		cout<<sum<<'\n';	  
	}      
}

Compilation message (stderr)

roadsideadverts.cpp: In function 'void dfs(ll, ll, ll)':
roadsideadverts.cpp:24:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(ll i = 0;i < v[x].size();i++){
      |               ~~^~~~~~~~~~~~~

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