Submission #887069

#	Time	Username	Problem	Language	Result	Execution time	Memory
887069		dwuy	Valley (BOI19_valley)	C++14	100 / 100	186 ms	65104 KiB

valley

/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;

int n, S, q, E;
int c[MX];
pii edges[MX];
vector<pii> G[MX];
bitset<MX> isS = 0;

void nhap(){
    cin >> n >> S >> q >> E;
    for(int i=1; i<n; i++){
        int u, v, w;
        cin >> u >> v >> w;
        edges[i] = {u, v};
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    for(int i=1; i<=S; i++){
        int u; cin >> u;
        isS[u] = 1;
    }
}

int dfsID = 0;
int h[MX];
int d[MX];
int num[MX];
int rnum[MX];
int clo[MX];
int dpDown[MX];
int p[MX][17];
int f[MX][17];
int mn[MX][17];

void dfs(int u){
    h[u] = h[p[u][0]] + 1;
    num[u] = ++dfsID;
    rnum[num[u]] = u;
    if(isS[u])  dpDown[u] = 0;
    else dpDown[u] = OO;
    pii best = {dpDown[u], 0};
    pii _best = {OO, 0};
    for(pii &tmp: G[u]){
        int v, c; tie(v, c) = tmp;
        if(v == p[u][0]) continue;
        p[v][0] = u;
        d[v] = d[u] + c;
        dfs(v);
        dpDown[u] = min(dpDown[u], dpDown[v] + c);
        if(dpDown[v] + c <= best.fi){
            _best = best;
            best = {dpDown[v] + c, v};
        }
        else _best = min(_best, {dpDown[v]+c, v});
    }
    for(pii &tmp: G[u]){
        int v, c; tie(v, c) = tmp;
        if(v == p[u][0]) continue;
        if(best.se == v) f[v][0] = d[u] - _best.fi;
        else f[v][0] = d[u] - best.fi;
    }
    clo[u] = dfsID;
}

int LCA(int u, int v){
    if(h[u] > h[v]) swap(u, v);
    for(int t=h[v] - h[u]; t; t-=-t&t) v = p[v][__lg(-t&t)];
    if(u == v) return u;
    for(int i=16; i>=0; i--) if(p[v][i] != p[u][i]){
        u = p[u][i];
        v = p[v][i];
    }
    return p[u][0];
}

int getMin(int l, int r){
    if(l>r) return OO;
    int k = __lg(r-l+1);
    return min(mn[l][k], mn[r-MASK(k)+1][k]);
}

void solve(){
    dfs(1);
    for(int j=1; j<=16; j++){
        for(int i=1; i<=n; i++){
            p[i][j] = p[p[i][j-1]][j-1];
            f[i][j] = max(f[i][j-1], f[p[i][j-1]][j-1]);
        }
    }
    for(int i=1; i<n; i++) if(h[edges[i].fi] > h[edges[i].se]){
        swap(edges[i].fi, edges[i].se);
    }
    for(int i=1; i<=n; i++){
        mn[i][0] = isS[rnum[i]]? d[rnum[i]] : OO;
    }
    for(int j=1; j<=16; j++){
        for(int i=1; i+MASK(j)-1<=n; i++){
            mn[i][j] = min(mn[i][j-1], mn[i+MASK(j-1)][j-1]);
        }
    }
    while(q--){
        int i, u;
        cin >> i >> u;
        int v = edges[i].se;
        int puv = LCA(u, v);
        int pue = LCA(u, E);

        if(!((LCA(u, v)==v || LCA(E, v)==v) && LCA(edges[i].fi, pue) == pue)){
            cout << "escaped\n";
            continue;
        }
        int res = OO;
        if(puv == v){
            res = dpDown[u];
            int mx = -1e18;
            int t = u;
            for(int i=16; i>=0; i--) if(h[p[u][i]]>=h[puv]){
                mx = max(mx, f[u][i]);
                u = p[u][i];
            }
            res = min(res, d[t] - mx);
        }
        else if(puv == u){
            res = min(getMin(num[u], num[v]-1), getMin(clo[v]+1, clo[u])) - d[u];
            int mx = -1e18;
            for(int i=16; i>=0; i--) if(p[u][i]!=0){
                mx = max(mx, f[u][i]);
                u = p[u][i];
            }
            res = min(res, d[puv] - mx);
        }
        else{
            int t = u;
            res = dpDown[u];
            int mx = -1e18;
            for(int i=16; i>=0; i--) if(h[p[u][i]] > h[puv]){
                mx = max(mx, f[u][i]);
                u = p[u][i];
            }
            res = min(res, d[t] - mx);
            res = min(res, d[t] - d[puv] + min(getMin(num[puv], num[v]-1), getMin(clo[v]+1, clo[puv])) - d[puv]);
            u = puv;
            mx = -1e18;
            for(int i=16; i>=0; i--) if(p[u][i]!=0){
                mx = max(mx, f[u][i]);
                u = p[u][i];
            }
            res = min(res, d[t] - mx);
        }
        if(res > 1e17) cout << "oo\n";
        else cout << res << endl;
    }
}

int32_t main(){
    fastIO;
//    file(TASK);

    nhap();
    solve();

//    system("fc test.out test.ans");
    return 0;
}

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