oj.uz

Submission #278788

# Submission time Handle Problem Language Result Execution time Memory
278788 2020-08-21T22:08:06 Z Haunted_Cpp Roadside Advertisements (NOI17_roadsideadverts) C++17
100 / 100
 206 ms 15736 KB 
/**
 *  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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8960 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 12664 KB Output is correct
2 Correct 193 ms 15608 KB Output is correct
3 Correct 163 ms 15736 KB Output is correct
4 Correct 177 ms 15608 KB Output is correct
5 Correct 173 ms 15608 KB Output is correct
6 Correct 185 ms 15736 KB Output is correct
7 Correct 185 ms 15608 KB Output is correct
8 Correct 174 ms 15608 KB Output is correct
9 Correct 169 ms 15620 KB Output is correct
10 Correct 185 ms 15608 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 10872 KB Output is correct
2 Correct 57 ms 14584 KB Output is correct
3 Correct 57 ms 14584 KB Output is correct
4 Correct 57 ms 14584 KB Output is correct
5 Correct 55 ms 14584 KB Output is correct
6 Correct 61 ms 14712 KB Output is correct
7 Correct 54 ms 14584 KB Output is correct
8 Correct 54 ms 14584 KB Output is correct
9 Correct 57 ms 14584 KB Output is correct
10 Correct 55 ms 14584 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8960 KB Output is correct
2 Correct 184 ms 12664 KB Output is correct
3 Correct 193 ms 15608 KB Output is correct
4 Correct 163 ms 15736 KB Output is correct
5 Correct 177 ms 15608 KB Output is correct
6 Correct 173 ms 15608 KB Output is correct
7 Correct 185 ms 15736 KB Output is correct
8 Correct 185 ms 15608 KB Output is correct
9 Correct 174 ms 15608 KB Output is correct
10 Correct 169 ms 15620 KB Output is correct
11 Correct 185 ms 15608 KB Output is correct
12 Correct 44 ms 10872 KB Output is correct
13 Correct 57 ms 14584 KB Output is correct
14 Correct 57 ms 14584 KB Output is correct
15 Correct 57 ms 14584 KB Output is correct
16 Correct 55 ms 14584 KB Output is correct
17 Correct 61 ms 14712 KB Output is correct
18 Correct 54 ms 14584 KB Output is correct
19 Correct 54 ms 14584 KB Output is correct
20 Correct 57 ms 14584 KB Output is correct
21 Correct 55 ms 14584 KB Output is correct
22 Correct 205 ms 13772 KB Output is correct
23 Correct 148 ms 11956 KB Output is correct
24 Correct 206 ms 14968 KB Output is correct
25 Correct 195 ms 14968 KB Output is correct
26 Correct 195 ms 14968 KB Output is correct
27 Correct 193 ms 14968 KB Output is correct
28 Correct 197 ms 15096 KB Output is correct
29 Correct 191 ms 14968 KB Output is correct
30 Correct 194 ms 14968 KB Output is correct
31 Correct 196 ms 14968 KB Output is correct