oj.uz

Submission #130963

# Submission time Handle Problem Language Result Execution time Memory
130963 2019-07-16T10:17:29 Z IOrtroiii Valley (BOI19_valley) C++14
100 / 100
 307 ms 36216 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll inf = 1e18;
const int N = 100100;

int n, m, q, root;
int from[N], to[N];
vector<pair<int, int>> g[N];
ll dep[N], down[N];
int par[17][N];
ll minPar[17][N];
int tin[N], tout[N], tt;

void dfs(int u) {
   for (int i = 1; i < 17; ++i) {
      par[i][u] = par[i - 1][par[i - 1][u]];
   }
   tin[u] = ++tt;
   for (auto e : g[u]) {
      int v, w;
      tie(v, w) = e;
      if (v != par[0][u]) {
         par[0][v] = u;
         dep[v] = dep[u] + w;
         dfs(v);
      }
   }
   tout[u] = tt;
}

bool isAnc(int u, int v) {
   return tin[u] <= tin[v] && tout[v] <= tout[u];
}

void dfsDown(int u) {
   for (auto e : g[u]) {
      int v, w;
      tie(v, w) = e;
      if (v != par[0][u]) {
         dfsDown(v);
         down[u] = min(down[u], down[v] + w);
      }
   }
   minPar[0][u] = down[u] - dep[u];
}

void debug(ll a[], string s) {
   cout << s << "\n";
   for (int i = 1; i <= n; ++i) {
      printf("%lld ", a[i]);
   }
   puts("");
}

int main() {
   scanf("%d %d %d %d", &n, &m, &q, &root);
   for (int i = 1; i < n; ++i) {
      int cost;
      scanf("%d %d %d", from + i, to + i, &cost);
      g[from[i]].emplace_back(to[i], cost);
      g[to[i]].emplace_back(from[i], cost);
   }
   par[0][root] = root;
   dfs(root);
   for (int i = 1; i <= n; ++i) {
      down[i] = inf;
   }
   while (m--) {
      int v;
      scanf("%d", &v);
      down[v] = 0;
   }
   dfsDown(root);
   for (int i = 1; i < 17; ++i) {
      for (int u = 1; u <= n; ++u) {
         minPar[i][u] = min(minPar[i - 1][u], minPar[i - 1][par[i - 1][u]]);
      }
   }
   for (int i = 1; i < n; ++i) {
      if (dep[from[i]] > dep[to[i]]) {
         swap(from[i], to[i]);
      }
   }
   while (q--) {
      int id, v;
      scanf("%d %d", &id, &v);
      if (!isAnc(to[id], v)) {
         puts("escaped");
         continue;
      }
      ll ans = down[to[id]] - dep[to[id]];
      int u = v;
      for (int i = 16; i >= 0; --i) {
         if (dep[par[i][u]] > dep[from[id]]) {
            ans = min(ans, minPar[i][u]);
            u = par[i][u];
         }
      }
      if (ans > (inf / 10)) {
         puts("oo");
      } else {
         printf("%lld\n", ans + dep[v]);
      }
   }
}

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:59:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d %d", &n, &m, &q, &root);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:62:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d", from + i, to + i, &cost);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:73:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &v);
       ~~~~~^~~~~~~~~~
valley.cpp:89:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &id, &v);
       ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2936 KB Output is correct
2 Correct 7 ms 3064 KB Output is correct
3 Correct 7 ms 3064 KB Output is correct
4 Correct 8 ms 3064 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2936 KB Output is correct
2 Correct 7 ms 3064 KB Output is correct
3 Correct 7 ms 3064 KB Output is correct
4 Correct 8 ms 3064 KB Output is correct
5 Correct 5 ms 3192 KB Output is correct
6 Correct 5 ms 3192 KB Output is correct
7 Correct 6 ms 3192 KB Output is correct
8 Correct 5 ms 3192 KB Output is correct
9 Correct 7 ms 3192 KB Output is correct
10 Correct 6 ms 3192 KB Output is correct
11 Correct 7 ms 3196 KB Output is correct
12 Correct 6 ms 3192 KB Output is correct
13 Correct 6 ms 3192 KB Output is correct
14 Correct 6 ms 3196 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 30344 KB Output is correct
2 Correct 217 ms 30040 KB Output is correct
3 Correct 232 ms 29944 KB Output is correct
4 Correct 257 ms 31092 KB Output is correct
5 Correct 307 ms 31096 KB Output is correct
6 Correct 270 ms 32120 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2936 KB Output is correct
2 Correct 7 ms 3064 KB Output is correct
3 Correct 7 ms 3064 KB Output is correct
4 Correct 8 ms 3064 KB Output is correct
5 Correct 5 ms 3192 KB Output is correct
6 Correct 5 ms 3192 KB Output is correct
7 Correct 6 ms 3192 KB Output is correct
8 Correct 5 ms 3192 KB Output is correct
9 Correct 7 ms 3192 KB Output is correct
10 Correct 6 ms 3192 KB Output is correct
11 Correct 7 ms 3196 KB Output is correct
12 Correct 6 ms 3192 KB Output is correct
13 Correct 6 ms 3192 KB Output is correct
14 Correct 6 ms 3196 KB Output is correct
15 Correct 211 ms 30344 KB Output is correct
16 Correct 217 ms 30040 KB Output is correct
17 Correct 232 ms 29944 KB Output is correct
18 Correct 257 ms 31092 KB Output is correct
19 Correct 307 ms 31096 KB Output is correct
20 Correct 270 ms 32120 KB Output is correct
21 Correct 185 ms 33744 KB Output is correct
22 Correct 207 ms 33308 KB Output is correct
23 Correct 219 ms 33244 KB Output is correct
24 Correct 233 ms 34444 KB Output is correct
25 Correct 242 ms 36216 KB Output is correct
26 Correct 230 ms 33780 KB Output is correct
27 Correct 227 ms 33340 KB Output is correct
28 Correct 211 ms 33272 KB Output is correct
29 Correct 218 ms 34168 KB Output is correct
30 Correct 260 ms 35128 KB Output is correct
31 Correct 192 ms 32504 KB Output is correct
32 Correct 266 ms 30188 KB Output is correct
33 Correct 216 ms 30164 KB Output is correct
34 Correct 232 ms 31736 KB Output is correct
35 Correct 291 ms 33528 KB Output is correct
36 Correct 242 ms 34404 KB Output is correct