Submission #224432

#	Time	Username	Problem	Language	Result	Execution time	Memory
224432		Haunted_Cpp	Valley (BOI19_valley)	C++17	100 / 100	291 ms	43260 KiB

valley

#include <cstdio>
#include <vector>
#include <bitset>
#include <cstring>
#include <cassert>

typedef long long i64;
using namespace std;

const int N = 1e5 + 5;

int n, s, q, e;

const i64 INF = 1e16;

vector< pair<int, pair<int, int> > > edge_list (N);
vector< pair<int, int> > g [N];
bitset<N> is_valid;
int in [N], out [N], tempo = 0, dp [N][20], depth[N];
i64 dist [N], subtree [N], magic [N], mn [N][20];

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

void calc_subtree (int node, int p = -1) {
  if (is_valid.test(node)) subtree[node] = dist[node];
  else subtree[node] = INF;
  for (auto to : g[node]) {
    if (to.first != p) {
      calc_subtree (to.first, node);
      subtree[node] = min (subtree[node], subtree[to.first]);
    }
  }
}

void build_dp (int node, int p = -1) {
  if (~p) mn[node][0] = magic[p];
  for (auto to : g[node]) {
    if (to.first != p) {
      build_dp (to.first, node);
    }
  }
}

bool in_between (int a, int b, int c) {
  return in[b] <= in[c] && out[b] >= out[c];
}

i64 Get (int lo, int hi) {
  const int diff = depth[hi] - depth[lo];
  assert (diff >= 0);
  i64 minimo = INF;
  for (int i = 0; i < 31; i++) {
    if ((diff >> i) & 1) {
      minimo = min (minimo, mn[hi][i]);
      hi = dp[hi][i];
    }
  }
  return minimo;
}

int main () {
  scanf ("%d %d %d %d", &n, &s, &q, &e);
  for (int i = 1; i < n; i++) {
    int st, et, w;
    scanf ("%d %d %d", &st, &et, &w);
    edge_list[i] = {st, {et, w}};
    g[st].emplace_back(et, w);
    g[et].emplace_back(st, w);
  }
  for (int i = 0; i < s; i++) {
    int loja;
    scanf ("%d", &loja);
    is_valid.set(loja);
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 20; j++) {
      mn[i][j] = 1e16;
      dp[i][j] = -1;
    }
  }
  dfs (e);
  calc_subtree (e);
  for (int i = 1; i <= n; i++) {
    magic[i] = subtree[i] - 2 * dist[i];
  }
  build_dp (e);
  for (int i = 1; i < 20; i++) {
    for (int j = 1; j <= n; j++) {
      if (dp[j][i - 1] != -1) {
        dp[j][i] = dp[dp[j][i - 1]][i - 1];
        mn[j][i] = min (mn[j][i - 1], mn[dp[j][i - 1]][i - 1]);
      }
    }
  } 
  while (q--) {
    int rua, loja;
    scanf ("%d %d", &rua, &loja);
    int st = edge_list[rua].first;
    int et = edge_list[rua].second.first;
    if (depth[st] > depth[et]) swap (st, et);
    assert (depth[et] > depth[st]);
    if (in_between (e, st, loja) == false || in_between (e, et, loja) == false) {
      puts("escaped");
      continue;
    }
    i64 primeiro = magic[loja] + dist[loja];
    i64 segundo = dist[loja] + Get (et, loja);
    if (min (primeiro, segundo) > 1e15) {
      puts("oo");
    } else {
      printf ("%lld\n", min (primeiro, segundo));
    }
  }   
  return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:73:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d %d %d", &n, &s, &q, &e);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:76:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d %d", &st, &et, &w);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:83:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &loja);
     ~~~~~~^~~~~~~~~~~~~
valley.cpp:108:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &rua, &loja);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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