Submission #786770

#	Time	Username	Problem	Language	Result	Execution time	Memory
786770		mgl_diamond	Valley (BOI19_valley)	C++17	100 / 100	403 ms	51932 KiB

valley

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

struct edge {
  int u, v, w;
  edge(int _u=0, int _v=0, int _w=0) : u(_u), v(_v), w(_w) {}
  int o(int t) { return u ^ v ^ t; }
};

const ll LINF = 1e18;
const int N = 1e5+5, LOG = 17, INF = 1e9;

int n, s, q, t;
bool shop[N];
vector<edge> e;
vector<int> graph[N];
int st[N], en[N], high[N], anc[N][LOG], cnt;
ll sum[N][LOG], best[N][LOG], dp[N];

void prep1(int u, int p) {
  st[u] = ++cnt;
  if (shop[u]) dp[u] = 0;
  else dp[u] = LINF;
  foru(i, 1, LOG-1) {
    anc[u][i] = anc[anc[u][i-1]][i-1];
    sum[u][i] = sum[u][i-1] + sum[anc[u][i-1]][i-1];
  } 
  fore(i, graph[u]) {
    int v = e[i].o(u);
    if (v == p) continue;
    anc[v][0] = u;
    sum[v][0] = e[i].w;
    high[v] = high[u] + 1;
    prep1(v, u);
    dp[u] = min(dp[u], dp[v] + e[i].w);
  }
  en[u] = cnt;
}

void prep2(int u, int p) {
  best[u][0] = min(dp[u], dp[anc[u][0]] + sum[u][0]);
  foru(i, 1, LOG-1) {
    best[u][i] = min(best[u][i-1], sum[u][i-1] + best[anc[u][i-1]][i-1]);
  }
  fore(i, graph[u]) {
    int v = e[i].o(u);
    if (v == p) continue;
    prep2(v, u);
  }
}

ll query(int u, int top) {
  ll sum_so_far = 0, ret = dp[u];
  ford(i, LOG-1, 0) {
    if (high[anc[u][i]] >= high[top]) {
      ret = min(ret, sum_so_far + best[u][i]);
      sum_so_far += sum[u][i];
      u = anc[u][i];
    }
  }
  return ret;
}

int main() {
  cin >> n >> s >> q >> t;
  foru(i, 2, n) {
    int u, v, w;
    cin >> u >> v >> w;
    graph[u].push_back(sz(e));
    graph[v].push_back(sz(e));
    e.emplace_back(u, v, w);
  }
  foru(i, 1, s) {
    int c;
    cin >> c;
    shop[c] = 1;
  }
  dp[0] = LINF;
  high[0] = -1;
  prep1(t, t);
  prep2(t, t);
  foru(r, 1, q) {
    int i, u;
    cin >> i >> u; --i;
    if (high[e[i].u] < high[e[i].v]) swap(e[i].u, e[i].v);
    int node = e[i].u;
    if (st[node] <= st[u] && st[u] <= en[node]) {
      ll ans = query(u, node);
      if (ans == LINF) cout << "oo\n";
      else cout << ans << "\n";
    } else cout << "escaped\n";
  }
}

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