Submission #1314666

#TimeUsernameProblemLanguageResultExecution timeMemory
1314666joshjuiceRoadside Advertisements (NOI17_roadsideadverts)C++20
100 / 100
34 ms10484 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;

#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define ppf pop_front
#define pf push_front
#define bk back()
#define frnt front()
#define ins insert
#define er erase
#define sc second
#define fr first
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define REP(i,n) for (int i = 0; i < n; ++i)
#define REP1(i,n) for (int i = 1; i <= n; ++i)
#define REPV(i,n) for (int i = n-1; i >= 0; --i)
#define REPV1(i, n) for (int i = n; i > 0; --i)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define MNTO(x,y) x = min(x, (__typeof__(x))y)
#define MXTO(x,y) x = max(x, (__typeof__(x))y)

const int MAXV = 5e4+5, LOG = 18;

int v, q, __ptr;
int parent[MAXV][LOG], depth[MAXV], dist[MAXV], pr[MAXV];
vector<pii> adj[MAXV];

void dfs(int u) {
  pr[u] = __ptr++;
  for (auto &[w, v] : adj[u]) {
    if (v == parent[u][0]) continue;
    parent[v][0] = u;
    depth[v] = depth[u]+1;
    dist[v] = dist[u]+w;
    dfs(v);
  }
}

int lca(int a, int b) {
  if (depth[a] < depth[b]) swap(a, b);
  REPV(j, LOG) {
    if (depth[parent[a][j]] >= depth[b]) a = parent[a][j];
  }
  if (a == b) return a;
  REPV(j, LOG) {
    if (parent[a][j] != parent[b][j]) {
      a = parent[a][j];
      b = parent[b][j];
    }
  }
  return parent[a][0];
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> v;
  REP(i, v-1) {
    int a, b, c;
    cin >> a >> b >> c;
    adj[a].eb(c, b);
    adj[b].eb(c, a);
  }
  dfs(0);
  REP(j, LOG-1) {
    REP(i, v) parent[i][j+1] = parent[parent[i][j]][j];
  }
  cin >> q;
  while (q--) {
    int a[5];
    REP(i, 5) cin >> a[i];
    sort(a, a+5, [&](int x, int y){return pr[x]<pr[y];});
    int c = a[0];
    REP(i, 4) c = lca(c, a[i+1]);
    int ans = dist[a[0]]-dist[c];
    REP(i, 4) {
      int common = lca(a[i], a[i+1]);
      ans += dist[a[i+1]]-dist[common];
    }
    cout << ans << '\n';
  }
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...