Submission #322153

#	Time	Username	Problem	Language	Result	Execution time	Memory
322153		Sparky_09	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	137 ms	20076 KiB

roadsideadverts

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

int n, l;
const int N = (int)1e5+5;
vector<int> graph[N], gdist[N], d(N), tin, tout;
int timer;
vector<vector<int>> up;

void dfs(int v, int p){
  tin[v] = ++timer;
  up[v][0] = p;
  for(int i = 1; i <= l; i++){
    up[v][i] = up[up[v][i-1]][i-1];
  }
  for(int i = 0; i < gdist[v].size(); i++){
    int loc = graph[v][i];
    if(loc==p) continue;
    d[loc]=d[v]+gdist[v][i];
    dfs(loc,v);
  }
  tout[v] = ++timer;
}

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

int lca(int u, int v){
  if(is_ancestor(u,v)) return u;
  if(is_ancestor(v,u)) return v;
  for(int i = l; i >= 0; --i){
    if(!is_ancestor(up[u][i], v)) u = up[u][i];
  }
  return up[u][0];
}

bool fun(int x, int y){
  return tin[x] < tin[y];
}

int dist(int x, int y){
  return d[x] + d[y] - 2 * d[lca(x, y)];
}
             
int main(){
  ios_base::sync_with_stdio(false);
  //freopen("input.txt", "r", stdin);
  cin >> n;
  for(int i = 0; i < n-1; i++){
    int x,y,d; cin>>x>>y>>d;
    graph[x].emplace_back(y); 
    graph[y].push_back(x);
    gdist[x].emplace_back(d); 
    gdist[y].push_back(d);
  }

  //preprocess
  tin.resize(n);
  tout.resize(n);
  timer = 0; 
  l = 18;
  up.assign(n, vector<int>(l+1));
  dfs(0,0);

  int quer;
  cin>>quer;
  while(quer--){
    vector<int> q(5);
    for(int i = 0; i < 5; i++) cin >> q[i];
    sort(q.begin(), q.end(), fun);
    int ans = 0;
    ans += dist(q[0], lca(q[4], q[0]));
    for(int i = 1; i < 5; i++){
      ans += dist(lca(q[i-1],q[i]), q[i]);
    }
    cout << ans << '\n';
  }
}

Compilation message (stderr)

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

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