Submission #496491

#	Time	Username	Problem	Language	Result	Execution time	Memory
496491		dsyz	Roadside Advertisements (NOI17_roadsideadverts)	C++17	7 / 100	96 ms	26280 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 dist[u];
	} 
	for(ll i = 19;i >= 0;i--){
		if(parent[i][u] != parent[i][v]){
			u = parent[i][u];
			v = parent[i][v];
	    }
	}
	return dist[parent[0][u]];
}
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();
  ll Q;
  cin>>Q;
  for(ll i = 0;i < Q;i++){
	  ll arr[5];
	  for(ll i = 0;i < 5;i++){
		  cin>>arr[i];
	  }
	  ll p[5];
	  memset(p,-1,sizeof(p));
	  for(ll j = 0;j < 5;j++){
		  for(ll z = 0;z < 20;z++){
			  if(parent[z][arr[j]] == arr[0]){
				  p[j] = arr[0];
				  break;
			  }else if(parent[z][arr[j]] == arr[1]){
				  p[j] = arr[1];
				  break;
			  }else if(parent[z][arr[j]] == arr[2]){
				  p[j] = arr[2];
				  break;
			  }else if(parent[z][arr[j]] == arr[3]){
				  p[j] = arr[3];
				  break;
			  }else if(parent[z][arr[j]] == arr[4]){
				  p[j] = arr[4];
				  break;
			  } 			  			  
		  }
		  if(p[j] == arr[j]){
			  p[j] = -1; //no parent that is in arr
		  }
		  //cout<<"PARENT OF "<<arr[j]<<" which is also among arr is "<<p[j]<<'\n';		  
	  }
	  ll sum = 0;
	  for(ll i = 0;i < 5;i++){
		  for(ll j = 0;j < 5;j++){
			  if(arr[i] != arr[j]){
				if(p[i] == arr[j]){
					ll a = lca(arr[i],arr[j]);
					sum += ((dist[arr[i]] + dist[arr[j]]) - (2 * a));				  				  
				}else if(p[i] == -1 && p[j] == -1 && i > j){
					//p[i] = MAXN + 5;
					//p[j] = MAXN + 5;
					ll a = lca(arr[i],arr[j]);
					sum += ((dist[arr[i]] + dist[arr[j]]) - (2 * 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: 0 / 23
• Subtask 3: 0 / 40
• Subtask 4: 0 / 30