Submission #1077460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077460		duckindog	Valley (BOI19_valley)	C++17	100 / 100	85 ms	34216 KiB

valley

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
const long long MAX = 1'000'000'000'000'000'000;
      
int n, s, q, e;
pair<int, int> edge[N];
vector<pair<int, int>> ad[N];
bool mk[N];

long long dp[N], d[N];
int sz[N], par[N];
void dfs(int u, int p = -1) { 
  dp[u] = (!mk[u] ? MAX : 0);
  for (const auto& [v, w] : ad[u]) { 
    if (v == p) continue;
    d[v] = d[u] + w;
    dfs(v, u);
    dp[u] = min(dp[u], dp[v] + w);
    par[v] = u;
    sz[u] += sz[v] + 1;
  }
}

int st[N], ed[N], it;
int head[N];
void hld(int u, int p = -1) { 
  st[u] = ++it;
  if (!head[u]) head[u] = u;

  sort(ad[u].begin(), ad[u].end(), [&](const auto& a, const auto& b) { 
    return sz[a.first] > sz[b.first];
  });

  bool heavy = false;
  for (const auto& [v, w] : ad[u]) { 
    if (v == p) continue;
    if (!heavy) head[v] = head[u], heavy = true;
    hld(v, u);
  }

  ed[u] = it;
}
inline bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }

long long f[N][18], lg[N];
void init() { 
  for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i <= n; ++i) f[st[i]][0] = dp[i] - d[i];
  for (int j = 1; j <= 17; ++j) { 
    for (int i = 1; i <= n - (1 << j) + 1; ++i)
      f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
  }
}
inline long long get(int l, int r) { 
  if (l > r) return MAX;
  int j = lg[r - l + 1];
  return min(f[l][j], f[r - (1 << j) + 1][j]);
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> s >> q >> e;
  for (int i = 1; i < n; ++i) { 
    int u, v, w; cin >> u >> v >> w;
    edge[i] = {u, v};
    ad[u].push_back({v, w});
    ad[v].push_back({u, w});
  }
  for (int i = 1; i <= s; ++i) { 
    int x; cin >> x;
    mk[x] = true;
  }

  dfs(par[e] = e); 
  hld(e);

  for (int i = 1; i < n; ++i) 
    if (anc(edge[i].second, edge[i].first)) swap(edge[i].first, edge[i].second);

  init();
  while (q--) { 
    int r, u; cin >> r >> u;
    int x = edge[r].second;
    if (!anc(x, u)) { cout << "escaped\n"; continue; }
    
    long long answer = MAX, depth = d[u];
    while (head[u] != head[x]) { 
      answer = min(answer, get(st[head[u]], st[u]) + depth);
      u = par[head[u]];
    } 
    answer = min(answer, get(st[x], st[u]) + depth);
    
    if (answer >= 1'000'000'000'000'000) { cout << "oo\n"; continue; }
    cout << answer << "\n";
  }
}

Compilation message (stderr)

valley.cpp: In function 'void init()':
valley.cpp:54:48: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   54 |       f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
      |                                              ~~^~~

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41