Submission #1096290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096290		tuandq	Valley (BOI19_valley)	C++17	0 / 100	99 ms	41044 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 {
    #define tiii tuple<int, int, int>

    const int LG = 17 ;

    int up[LG][N], h[N], st[N], en[N], in[N], dfscnt = 0 ;
    pll dp[N << 1], g[N] ;
    vector<tiii> ke[N] ;
    bool mark[N] ;
    ll dis[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[v][0] = u ;
                in[v] = i ;
                dfs(v, 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[u][k] ;
            if(!inside(nxt, v)) {
                u = nxt ;
            }
        }
        return up[u][0] ;
    }

    void modify(pll &cur, ll x) {
        if(x <= cur.fi) {
            cur.se = cur.fi ;
            cur.fi = x ;
        }
        else minimize(cur.se, x) ;
    }

    pll get_dp(int u, int par, int idx) {
        if(idx != -1 && dp[idx].fi != -1ll) {
            return dp[idx] ;
        }

        pll res(mark[u] ? 0ll : INF, INF) ;
        // cerr << u << ' ' << par << ' ' << idx << ' ' << mark[u] << ' ' << res.fi << ' ' << res.se << endl ;
        for(tiii cur : ke[u]) {
            int v = get<0>(cur) ;
            int w = get<1>(cur) ;
            int nxt = get<2>(cur) ;
            if(v != par) {
                modify(res, get_dp(v, u, nxt).fi + w) ;
            }
        }

        if(idx != -1) {
            dp[idx] = res ;
        }
        return res ;
    }

    ll get_dis(int u, int v) {
        return dis[u] + dis[v] - 2ll * dis[get_lca(u, v)] ;
    }

    int get_idx(int i, int u, int v) {
        return i * 2 - (e[i].u == u) ;
    }

    void print(ll x) {
        if(x >= INF) {
            cout << "oo\n" ; return ;
        }
        cout << x << '\n' ;
    }
    void trySolve(int del, int town) {
        int u = e[del].u ;
        int v = e[del].v ;
        if(h[u] > h[v]) swap(u, v) ;
        if(!inside(v, town)) {
            cout << "escaped\n" ; return ;
        }

        int idx1 = get_idx(del, u, v) ;
        ll len = get_dis(town, u) + get_dp(u, -1, idx1).fi ;
        cerr << idx1 << ' ' << len << ' ' << g[town].fi << '\n' ;
        if(g[town].fi != len && len < INF) {
            print(g[town].fi) ;
            // cout << "tron\n" ;
            return ;
        }

        int p = up[u][0] ;
        int idx2 = get_idx(in[u], p, v) ;
        pll x = get_dp(p, -1, idx2) ;
        ll y = get_dp(u, -1, idx1).fi + e[in[u]].w ;

        if(g[town].se >= INF) {
            print(INF) ;
        }
        else {
            print(min(g[town].se, get_dis(u, p) + (x.fi != y ? x.fi : x.se))) ;
        }
    }

    void solve() {
        for(int i = 1; i <= m; i ++) {
            mark[a[i]] = true ;
        }
        for(int i = 1; i < n; i ++) {
            ke[e[i].u].emplace_back(e[i].v, e[i].w, i * 2 - 1) ;
            ke[e[i].v].emplace_back(e[i].u, e[i].w, i * 2) ;
            dp[i * 2 - 1] = dp[i * 2] = mp(-1ll, -1ll) ;
        }
        for(int i = 1; i <= n; i ++) {
            g[i] = get_dp(i, 0, -1) ;
        }

        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]] ;
            }
        }

        for(int i = 1; i <= q; i ++) {
            trySolve(query[i].fi, query[i].se) ;
        }
    }
}

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:204:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |         freopen(taskname".inp", "r", stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:205:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  205 |         freopen(taskname".out", "w", stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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