Submission #670887

#	Time	Username	Problem	Language	Result	Execution time	Memory
670887		chanhchuong123	Valley (BOI19_valley)	C++17	100 / 100	221 ms	40196 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define task "C"
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}

const long long INF = 2e18;
const int N = 1e5 + 4;
int n, s, q, ex, timer;
int h[N], tin[N], tout[N];
int isShop[N], par[18][N];
vector<pair<int, int>> adj[N];
pair<pair<int, int>, int> e[N];
long long dp[N], Min[18][N], dep[N];

void dfs(int u, int p) {
    tin[u] = ++timer;
    dp[u] = isShop[u] ? 0 : INF;
    for (auto [v, w]: adj[u]) if (v != p) {
        dep[v] = dep[u] + w;
        h[v] = h[u] + 1;
        par[0][v] = u;
        dfs(v, u);
        mini(dp[u], dp[v] + w);
    }
    tout[u] = timer;
    for (int j = 1; j <= 17; j++) Min[j][u] = INF;
}

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

void pre_dfs(int u) {
    for (auto [v, w]: adj[u]) if (v != par[0][u]) {
        Min[0][v] = dp[u] - dep[u];
        for (int j = 1; j <= 17; j++) {
            par[j][v] = par[j - 1][par[j - 1][v]];
            Min[j][v] = min(Min[j - 1][v], Min[j - 1][par[j - 1][v]]);
        }
        pre_dfs(v);
    }
}

long long calc(int u, int p) {
    int k = h[u] - h[p]; long long res = dp[u] - dep[u];
    for (int j = 0; (1 << j) <= k; j++) if (k >> j & 1) {
        res = min(res, Min[j][u]); u = par[j][u];
    }
    return res;
}

main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  if (fopen(task".inp","r")) {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }

    cin >> n >> s >> q >> ex;
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        e[i] = {{u, v}, w};
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int i = 1, x; i <= s; i++) {
        cin >> x; isShop[x] = true;
    }
    dfs(ex, -1); pre_dfs(ex);

    while (q--) {
        int I, R; cin >> I >> R;
        int u = e[I].fi.fi;
        int v = e[I].fi.se;
        if (tin[u] < tin[v]) swap(u, v);
        if (!isAncestor(u, R)) cout << "escaped\n";
        else {
            long long ans = calc(R, u) + dep[R];
            if (ans >= INF) cout << "oo\n";
            else cout << ans << '\n';
        }
    }
}

Compilation message (stderr)

valley.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   62 | main() {
      | ^~~~
valley.cpp: In function 'int main()':
valley.cpp:67:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:68:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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