oj.uz

Submission #123013

# Submission time Handle Problem Language Result Execution time Memory
123013 2019-06-30T01:55:35 Z model_code Valley (BOI19_valley) C++17
100 / 100
 807 ms 43140 KB 
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 200005;
const int maxlg = 20;
const ll inf = 1LL << 60;

vector<pair<int, ll>> adj [maxn];
ll height [maxn];
int lvl [maxn];
ll dp [maxn];
bool store [maxn];
int start_time [maxn];
int end_time [maxn];
int cur_time;

void build_dp (int vertex, int parent, ll cur_height) {
  cur_time++;
  start_time[vertex] = cur_time;
  
  height[vertex] = cur_height;
  lvl[vertex] = lvl[parent] + 1;
  for (pair<int, ll> nxt : adj[vertex]) {
    if (nxt.first != parent) {
      build_dp(nxt.first, vertex, cur_height + nxt.second);
    }
  }

  if (store[vertex]) {
    dp[vertex] = height[vertex];
  } else {
    dp[vertex] = inf;
    for (pair<int, ll> nxt : adj[vertex]) {
      if (nxt.first != parent) {
        dp[vertex] = min(dp[vertex], dp[nxt.first]);
      }
    }
  }

  end_time[vertex] = cur_time;
}

bool is_parent (int u, int par) {
  return start_time[par] <= start_time[u] && end_time[u] <= end_time[par];
}

int jmp [maxn][maxlg];
ll ans_jmp [maxn][maxlg];

void build_jmp (int vertex, int parent) {
  jmp[vertex][0] = parent;
  if (dp[vertex] == inf) {
    ans_jmp[vertex][0] = inf;
  } else {
    ans_jmp[vertex][0] = dp[vertex] - 2 * height[vertex];
  }

  for (int i = 1; i < maxlg; i++) {
    jmp[vertex][i] = jmp[jmp[vertex][i - 1]][i - 1];
    ans_jmp[vertex][i] = min(ans_jmp[vertex][i - 1], ans_jmp[jmp[vertex][i - 1]][i - 1]);
  }

  for (pair<int, ll> nxt : adj[vertex]) {
    if (nxt.first != parent) {
      build_jmp(nxt.first, vertex);
    }
  }
}

ll query (int vertex, int forb) {
  if (!is_parent(vertex, forb)) {
    return -1;
  }

  ll cur_h = height[vertex];
  
  int diff = lvl[vertex] - lvl[forb];
  ll ans = inf;
  for (int i = maxlg - 1; i >= 0; i--) {
    if (diff & 1 << i) {
      ans = min(ans, ans_jmp[vertex][i]);
      vertex = jmp[vertex][i];
    }
  }
  ans = min(ans, ans_jmp[vertex][0]);

  if (ans != inf) {
    ans += cur_h;
  }
  
  return ans;
}

int main () {
  int vertexc, storec, queryc, root;
  cin >> vertexc >> storec >> queryc >> root;

  vector<pair<int, int>> edges;
  for (int i = 0; i < vertexc - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;

    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
    edges.push_back(make_pair(u, v));
  }

  for (int i = 0; i < storec; i++) {
    int x;
    cin >> x;
    store[x] = true;
  }

  build_dp(root, root, 0);
  build_jmp(root, root);
  
  for (int i = 0; i < vertexc - 1; i++) {
    if (lvl[edges[i].first] < lvl[edges[i].second]) {
      swap(edges[i].first, edges[i].second);
    }
  }
  
  for (int i = 0; i < queryc; i++) {
    int forb_id, cur_vertex;
    cin >> forb_id >> cur_vertex;

    ll ans = query(cur_vertex, edges[forb_id - 1].first);
    if (ans == -1) {
      cout << "escaped" << '\n';
    } else if (ans == inf) {
      cout << "oo" << '\n';
    } else {
      cout << ans << '\n';
    }
  }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5240 KB Output is correct
2 Correct 40 ms 5116 KB Output is correct
3 Correct 41 ms 5240 KB Output is correct
4 Correct 40 ms 5112 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5240 KB Output is correct
2 Correct 40 ms 5116 KB Output is correct
3 Correct 41 ms 5240 KB Output is correct
4 Correct 40 ms 5112 KB Output is correct
5 Correct 11 ms 5368 KB Output is correct
6 Correct 11 ms 5368 KB Output is correct
7 Correct 11 ms 5496 KB Output is correct
8 Correct 11 ms 5368 KB Output is correct
9 Correct 11 ms 5368 KB Output is correct
10 Correct 11 ms 5368 KB Output is correct
11 Correct 11 ms 5368 KB Output is correct
12 Correct 12 ms 5368 KB Output is correct
13 Correct 12 ms 5368 KB Output is correct
14 Correct 11 ms 5368 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 38208 KB Output is correct
2 Correct 740 ms 37892 KB Output is correct
3 Correct 761 ms 38124 KB Output is correct
4 Correct 799 ms 39920 KB Output is correct
5 Correct 759 ms 40144 KB Output is correct
6 Correct 807 ms 42340 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5240 KB Output is correct
2 Correct 40 ms 5116 KB Output is correct
3 Correct 41 ms 5240 KB Output is correct
4 Correct 40 ms 5112 KB Output is correct
5 Correct 11 ms 5368 KB Output is correct
6 Correct 11 ms 5368 KB Output is correct
7 Correct 11 ms 5496 KB Output is correct
8 Correct 11 ms 5368 KB Output is correct
9 Correct 11 ms 5368 KB Output is correct
10 Correct 11 ms 5368 KB Output is correct
11 Correct 11 ms 5368 KB Output is correct
12 Correct 12 ms 5368 KB Output is correct
13 Correct 12 ms 5368 KB Output is correct
14 Correct 11 ms 5368 KB Output is correct
15 Correct 726 ms 38208 KB Output is correct
16 Correct 740 ms 37892 KB Output is correct
17 Correct 761 ms 38124 KB Output is correct
18 Correct 799 ms 39920 KB Output is correct
19 Correct 759 ms 40144 KB Output is correct
20 Correct 807 ms 42340 KB Output is correct
21 Correct 672 ms 38060 KB Output is correct
22 Correct 686 ms 37872 KB Output is correct
23 Correct 714 ms 37996 KB Output is correct
24 Correct 793 ms 40104 KB Output is correct
25 Correct 740 ms 43140 KB Output is correct
26 Correct 681 ms 38156 KB Output is correct
27 Correct 695 ms 37908 KB Output is correct
28 Correct 706 ms 38124 KB Output is correct
29 Correct 742 ms 39784 KB Output is correct
30 Correct 767 ms 41256 KB Output is correct
31 Correct 683 ms 38220 KB Output is correct
32 Correct 694 ms 38000 KB Output is correct
33 Correct 713 ms 38380 KB Output is correct
34 Correct 748 ms 40168 KB Output is correct
35 Correct 755 ms 43048 KB Output is correct
36 Correct 698 ms 40644 KB Output is correct