oj.uz

답안 #224432

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
224432 2020-04-17T22:01:00 Z Haunted_Cpp Valley (BOI19_valley) C++17
100 / 100
 291 ms 43260 KB 
#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

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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 27520 KB Output is correct
2 Correct 22 ms 27520 KB Output is correct
3 Correct 26 ms 27520 KB Output is correct
4 Correct 25 ms 27520 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 27520 KB Output is correct
2 Correct 22 ms 27520 KB Output is correct
3 Correct 26 ms 27520 KB Output is correct
4 Correct 25 ms 27520 KB Output is correct
5 Correct 21 ms 27520 KB Output is correct
6 Correct 20 ms 27392 KB Output is correct
7 Correct 20 ms 27520 KB Output is correct
8 Correct 26 ms 27520 KB Output is correct
9 Correct 23 ms 27520 KB Output is correct
10 Correct 20 ms 27520 KB Output is correct
11 Correct 20 ms 27520 KB Output is correct
12 Correct 21 ms 27520 KB Output is correct
13 Correct 20 ms 27512 KB Output is correct
14 Correct 23 ms 27520 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 220 ms 36344 KB Output is correct
2 Correct 201 ms 38976 KB Output is correct
3 Correct 212 ms 39032 KB Output is correct
4 Correct 242 ms 40696 KB Output is correct
5 Correct 256 ms 40920 KB Output is correct
6 Correct 272 ms 42708 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 27520 KB Output is correct
2 Correct 22 ms 27520 KB Output is correct
3 Correct 26 ms 27520 KB Output is correct
4 Correct 25 ms 27520 KB Output is correct
5 Correct 21 ms 27520 KB Output is correct
6 Correct 20 ms 27392 KB Output is correct
7 Correct 20 ms 27520 KB Output is correct
8 Correct 26 ms 27520 KB Output is correct
9 Correct 23 ms 27520 KB Output is correct
10 Correct 20 ms 27520 KB Output is correct
11 Correct 20 ms 27520 KB Output is correct
12 Correct 21 ms 27520 KB Output is correct
13 Correct 20 ms 27512 KB Output is correct
14 Correct 23 ms 27520 KB Output is correct
15 Correct 220 ms 36344 KB Output is correct
16 Correct 201 ms 38976 KB Output is correct
17 Correct 212 ms 39032 KB Output is correct
18 Correct 242 ms 40696 KB Output is correct
19 Correct 256 ms 40920 KB Output is correct
20 Correct 272 ms 42708 KB Output is correct
21 Correct 156 ms 38776 KB Output is correct
22 Correct 170 ms 38392 KB Output is correct
23 Correct 201 ms 38520 KB Output is correct
24 Correct 291 ms 40440 KB Output is correct
25 Correct 229 ms 43260 KB Output is correct
26 Correct 161 ms 38776 KB Output is correct
27 Correct 178 ms 38392 KB Output is correct
28 Correct 192 ms 38532 KB Output is correct
29 Correct 264 ms 39800 KB Output is correct
30 Correct 236 ms 41208 KB Output is correct
31 Correct 156 ms 38776 KB Output is correct
32 Correct 190 ms 38520 KB Output is correct
33 Correct 212 ms 38648 KB Output is correct
34 Correct 222 ms 40312 KB Output is correct
35 Correct 234 ms 43128 KB Output is correct
36 Correct 198 ms 40440 KB Output is correct