Submission #130963

#	Time	Username	Problem	Language	Result	Execution time	Memory
130963		IOrtroiii	Valley (BOI19_valley)	C++14	100 / 100	307 ms	36216 KiB

valley

#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 (stderr)

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 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41