Submission #766542

#	Time	Username	Problem	Language	Result	Execution time	Memory
766542		BeanZ	Valley (BOI19_valley)	C++14	100 / 100	259 ms	58376 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1e5 + 5;
long long mod = 998244353;
const int lim = 4e5 + 5;
const int lg = 22;
const int base = 311;
const long double eps = 1e-6;
struct viet{
    ll u, v, w;
};
vector<viet> E;
ll dp[N][lg + 1], par[N][lg + 1], dep[N], a[N], dep2[N];
vector<pair<ll, ll>> node[N];
void dfs2(ll u, ll p){
    for (int i = 1; i <= lg; i++){
        dp[u][i] = min(dp[u][i - 1], dp[par[u][i - 1]][i - 1]);
    }
    for (auto j : node[u]){
        if (j.first == p) continue;
        dfs2(j.first, u);
    }
}
void dfs(ll u, ll p){
    for (int i = 1; i <= lg; i++){
        par[u][i] = par[par[u][i - 1]][i - 1];
    }
    dp[u][0] = 1e18;
    for (auto j : node[u]){
        if (j.first == p) continue;
        par[j.first][0] = u;
        dep[j.first] = dep[u] + j.second;
        dep2[j.first] = dep2[u] + 1;
        dfs(j.first, u);
        dp[u][0] = min(dp[u][0], dp[j.first][0] + j.second * 2);
    }
    if (a[u]) dp[u][0] = -dep[u];
}
ll check(ll u, ll v){
    ll dist = dep2[v] - dep2[u];
    if (dist < 0) return 0;
    for (int i = 0; i <= lg; i++){
        if (dist & (1 << i)){
            v = par[v][i];
        }
    }
    if (v == u) return 1;
    else return 0;
}
ll get(ll u, ll v){
    ll dist = dep2[u] - dep2[v];
    ll res = 1e18;
    ll dd = dep[u];
    for (int i = 0; i <= lg; i++){
        if (dist & (1 << i)){
            res = min(res, dd + dp[u][i]);
            u = par[u][i];
        }
    }
    res = min(res, dd + dp[u][0]);
    return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n, s, q, e;
    cin >> n >> s >> q >> e;
    for (int i = 1; i < n; i++){
        ll u, v, w;
        cin >> u >> v >> w;
        E.push_back({u, v, w});
        node[u].push_back({v, w});
        node[v].push_back({u, w});
    }
    for (int i = 1; i <= s; i++){
        ll x;
        cin >> x;
        a[x] = 1;
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= lg; j++){
            dp[i][j] = 1e18;
        }
    }
    dfs(e, e);
    dfs2(e, e);
    while (q--){
        ll u, v;
        cin >> v >> u;
        ll n1 = E[v - 1].u;
        ll n2 = E[v - 1].v;
        if (dep[n1] < dep[n2]) swap(n1, n2);
        if (!check(n1, u)) cout << "escaped" << endl;
        else {
            ll x = get(u, n1);
            if (x > 1e17) cout << "oo" << endl;
            else cout << x << endl;
        }
    }
}
/*
Ans:
 
Out:
*/

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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