Submission #798432

#	Time	Username	Problem	Language	Result	Execution time	Memory
798432		HunterXD	Roadside Advertisements (NOI17_roadsideadverts)	C++17	7 / 100	80 ms	20404 KiB

roadsideadverts

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

typedef int ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;

#define all(x) x.begin(), x.end()
#define pb push_back

const char nd = '\n';

struct edge {
  ll v, w;
};

vector<vector<edge>> graph;
vl level;
vvl sparse, dist;

void dfs(ll u, ll p) {
  sparse[u][0] = p;
  for (auto v : graph[u]) {
    if (v.v == p) continue;
    dist[v.v][0] = v.w;
    level[v.v] = level[u] + 1;
    dfs(v.v, u);
  }
}

void calc(ll n) {
  for (ll i = 1; i < 30; i++) {
    for (ll j = 1; j <= n; j++) {
      sparse[j][i] = sparse[sparse[j][i - 1]][i - 1];
      dist[j][i] = dist[j][i - 1] + dist[sparse[j][i - 1]][i - 1];
    }
  }
}

pair<ll, ll> up(ll u, ll d) {
  ll i = 0;
  ll suma = 0;

  while (d) {
    if (d & 1) {
      suma += dist[u][i];
      u = sparse[u][i];
    }
    i++;
    d >>= 1;
  }

  return make_pair(u, suma);
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  //
  ll n;
  cin >> n;

  graph.assign(n + 1, vector<edge>());
  level.assign(n + 1, 0);
  sparse.assign(n + 1, vl(30, 0));
  dist.assign(n + 1, vl(30, 0));

  ll u, v, w;
  for (ll i = 1; i < n; i++) {
    cin >> u >> v >> w;
    u++, v++;
    graph[u].pb({v, w});
    graph[v].pb({u, w});
  }

  dfs(1, 0);

  ll q;
  cin >> q;

  vl a(5);

  calc(n);

  while (q--) {
    for (auto &v : a) cin >> v, v++;

    ll res = 0;
    pair<ll, ll> temp;
    for (auto v : a) {
      ll ans = 0, lev = -1000000;
      for (auto u : a) {
        if (level[v] - level[u] > 0 && level[u] > lev) {
          temp = up(v, level[v] - level[u]);
          if (temp.first == u) {
            ans = temp.second;
            lev = level[u];
          }
        }
      }
      res += ans;
    }
    cout << res << nd;
  }
}

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