Submission #1096450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096450		tuandq	Valley (BOI19_valley)	C++17	100 / 100	109 ms	46000 KiB

valley

#include <bits/stdc++.h>
using namespace std ;

typedef long long ll ;
typedef long double ld ;
typedef pair<int, int> pii ;
typedef pair<int, long long> pil ;
typedef pair<long long, int> pli ;
typedef pair<long long, long long> pll ;
typedef vector<int> vi ;
typedef vector<long long> vll ;

#define bitc(n) (__builtin_popcountll(n))
#define clz(n) (__builtin_clzll(n))
#define ctz(n) (__builtin_ctzll(n))
#define lg(n) (31 - __builtin_clz(n))
#define MASK(k) (1ll << (k))
#define getbit(n, k) ((n) >> (k) & 1)
#define flipbit(n, k) ((n) ^ (1ll << (k)))
#define ton(n, k) ((n) | (1ll << (k)))
#define toff(n, k) ((n) & ~(1ll << (k)))

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define lwb lower_bound
#define upb upper_bound
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define taskname "input"

template<class X, class Y> bool maximize(X &x, const Y &y) {return (x < y ? x = y, true : false) ;}
template<class X, class Y> bool minimize(X &x, const Y &y) {return (x > y ? x = y, true : false) ;}

template<class X>
void remove_dup(vector<X> &ve) {
    sort(ve.begin(), ve.end()) ;
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin()) ;
}

const ll mod = 1e9 + 7 ;
const ll INF = 1e18 ;
const int inf = 1e9 ;
const int N = 1e5 + 5 ;

/* Some Peach Tea Is Great ;-; */
/* Author : Tuandq */

struct E {
    int u, v, w ;
    E() {}
    E(int _u, int _v, int _w): u(_u), v(_v), w(_w) {}  
};

int a[N], n, m, q, hel ;
vector<int> adj[N] ;
pii query[N] ;
E e[N] ;

namespace sub4 {
    const int LG = 17 ;

    int st[N], en[N], h[N], dfscnt = 0 ;
    ll dis[N], dp[N] ;
    pil up[LG][N] ;

    void dfs(int u, int par) {
        st[u] = ++dfscnt ;
        for(int i : adj[u]) {
            int v = e[i].u ^ e[i].v ^ u ;
            if(v != par) {
                dis[v] = dis[u] + e[i].w ;
                h[v] = h[u] + 1 ;
                up[0][v].fi = u ;
                dfs(v, u) ;
                minimize(dp[u], dp[v] + 1ll * e[i].w) ;
            }
        }
        up[0][u].se = dp[u] - dis[u] ;
        en[u] = dfscnt ;
    }

    bool inside(int u, int v) {
        return st[u] <= st[v] && en[v] <= en[u] ;
    }
    int get_lca(int u, int v) {
        if(inside(u, v)) return u ;
        for(int k = lg(u) - 1; k > -1; k --) {
            int nxt = up[k][u].fi ;
            if(!inside(nxt, v)) {
                u = nxt ;
            }
        }
        return up[0][u].fi ;
    }

    pil go_up(int u, int k) {
        ll res = INF ;
        for(int j = lg(k); j > -1; j --) {
            if(k >> j & 1) {
                minimize(res, up[j][u].se) ;
                u = up[j][u].fi ;
            }
        }
        // minimize(res, up[0][u].se) ;
        return mp(u, res) ;
    }

    ll trySolve(int del, int town) {
        int u = e[del].u ;
        int v = e[del].v ;
        if(st[u] > st[v]) swap(u, v) ;

        if(!inside(v, town)) {
            return -1ll ;
        }

        int k = h[town] - h[u] ;
        return go_up(town, k).se + dis[town] ;
    }

    void solve() {
        for(int i = 1; i <= n; i ++) {
            dp[i] = INF ;
            for(int j = 0; (1 << j) <= n; j ++) {
                up[j][i].se = INF ;
            }
        }
        for(int i = 1; i <= m; i ++) {
            dp[a[i]] = 0 ;
        }

        dfs(hel, 0) ;
        for(int j = 1; (1 << j) <= n; j ++) {
            for(int i = 1; i <= n; i ++) {
                up[j][i] = up[j - 1][up[j - 1][i].fi] ;
                minimize(up[j][i].se, up[j - 1][i].se) ;
            }
        }

        for(int i = 1; i <= q; i ++) {
            ll x = trySolve(query[i].fi, query[i].se) ;
            if(x == -1) {
                cout << "escaped\n" ;
            }
            else if(x >= INF) {
                cout << "oo\n" ;
            }
            else {
                cout << x << '\n' ;
            }
        }
        // cerr << 1.0 * clock() << " ms" ;
    }
}

signed main() {
    ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
    if(fopen(taskname".inp", "r")) {
        freopen(taskname".inp", "r", stdin) ;
        freopen(taskname".out", "w", stdout) ;
    }

    cin >> n >> m >> q >> hel ;
    for(int i = 1; i < n; i ++) {
        int u, v, w ; cin >> u >> v >> w ;
        adj[u].push_back(i) ;
        adj[v].push_back(i) ;
        e[i] = E(u, v, w) ;
    }
    for(int i = 1; i <= m; i ++) {
        cin >> a[i] ;
    }
    for(int i = 1; i <= q; i ++) {
        cin >> query[i].fi >> query[i].se ;
    }

    return sub4::solve(), 0 ;
}

Compilation message (stderr)

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

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