Submission #278788

#	Time	Username	Problem	Language	Result	Execution time	Memory
278788		Haunted_Cpp	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	206 ms	15736 KiB

roadsideadverts

/**
 *  author: Haunted_Cpp
**/
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif

const int MAX_N = 5e4 + 5;
const int MAX_K = 20 + 5;

int Time = 0;
vector<int> depth(MAX_N), dist(MAX_N), in(MAX_N), out(MAX_N);
vector<vector<int>> dp(MAX_N, vector<int>(MAX_K, -1));
vector<vector<pair<int, int>>> g(MAX_N);

void dfs(int node = 0, int p = -1) {
  in[node] = ++Time;
  dp[node][0] = p;
  for (auto to : g[node]) {
    if (to.first != p) {
      depth[to.first] = depth[node] + 1;
      dist[to.first] = dist[node] + to.second;
      dfs(to.first, node);
    }
  }
  out[node] = Time;
}

int kth(int node, int diff) {
  assert(diff >= 0);
  for (int i = MAX_K - 1; ~i; i--) {
    if ((diff >> i) & 1) {
      node = dp[node][i];
    }
  }
  return node;
}

int lca(int u, int v) {
  if (depth[u] < depth[v]) swap(u, v);
  u = kth(u, depth[u] - depth[v]);
  if (u == v) return u;
  for (int i = MAX_K - 1; ~i; i--) {
    if (dp[u][i] != dp[v][i]) {
      u = dp[u][i];
      v = dp[v][i];
    }
  }
  return dp[u][0];
}

int get_dist(int u, int v) {
  return dist[u] + dist[v] - 2 * dist[lca(u, v)];
}

bool in_subtree(int u, int v) {
  return (in[u] <= in[v] && out[u] >= out[v]);
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); 
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int st, et, w;
    cin >> st >> et >> w;
    g[st].emplace_back(et, w);
    g[et].emplace_back(st, w);
  }
  dfs();
  for (int j = 1; j < MAX_K; j++) {
    for (int i = 0; i < n; i++) {
      if (~dp[i][j - 1]) {
        dp[i][j] = dp[dp[i][j - 1]][j - 1];
      }
    }
  }
  int q;
  cin >> q;
  const int T = 5;
  vector<int> arr(T);
  while(q--) {
    for (int i = 0; i < T; i++) cin >> arr[i];
    vector<pair<int, int>> check;
    for (int i = 0; i < T; i++) {
      for(int j = 0; j < T; j++) {
        const int LCA = lca(arr[i], arr[j]);
        check.emplace_back(depth[LCA], LCA);
      }
    }
    sort(check.begin(), check.end());
    check.erase(unique(check.begin(), check.end()), check.end());
    set<int> vis;
    function<int(int)> solve = [&](int source) {
      vis.insert(source);
      const int d = depth[source];
      int s = 0;
      for (auto to : check) {
        const int TO = to.second;
        if(vis.find(TO) != vis.end()) continue;
        if (d <= depth[TO] && in_subtree(source, TO)) {
          vis.insert(TO);
          s += get_dist(source, TO) + solve(TO);
        }
      }
      return s;
    };
    cout << solve(check[0].second) << '\n';
  }
  return 0;
}

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