Submission #873780

#	Time	Username	Problem	Language	Result	Execution time	Memory
873780		hqminhuwu	Valley (BOI19_valley)	C++14	100 / 100	128 ms	145792 KiB

valley

#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e17;
const ll mod = 1e9 + 7;

ll bg[N],ed[N],dp[N],dep[N],d[N],up[20][N],updp[20][N],cnt;
vector <pll> a[N],edge;
void dfs (int u, int p){
    bg[u] = ++cnt;
    for (pii k : a[u]){
        int w = k.nd, v = k.st;
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        d[v] = d[u] + w;
        up[0][v] = u;
        dfs(v,u);
        dp[u] = min (dp[u],dp[v] + w);
    }
    ed[u] = cnt;
}

void dfs1 (int u, int p){
    for (pii k : a[u]){
        int w = k.nd, v = k.st;
        if (v == p) continue;
        updp[0][v] = dp[u] - d[u];
        dfs1(v,u);
    }
}

bool anc (int u, int v){
    return (bg[u] <= bg[v]) && (ed[u] >= ed[v]);
}


ll jump (int u, int v) {
    ll ans = oo,i;
    ford (i,18,0) 
    if (v & (1 << i)){
        ans = min(ans, updp[i][u]);
        u = up[i][u];
    }
    return ans;
}

ll n,s,q,e,i,j,u,v,w;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> s >> q >> e;
    forf (i,1,n) {
        cin >> u >> v >> w;
        edge.pb({u, v});
        a[u].pb({v, w});
        a[v].pb({u, w});
    }
    forr (j,0,18)
    forr (i,1,n)
        updp[j][i] = oo;
    forr (i,1,n)
        dp[i] = oo;
    forr (i,1,s)
        cin >> u, dp[u] = 0;
    dfs(e,e);
    dfs1(e,e);
    forr (j,1,18)
    forr (i,1,n)
        up[j][i] = up[j - 1][up[j - 1][i]],
        updp[j][i] = min(updp[j - 1][i],updp[j - 1][up[j - 1][i]]);
    forf (i,0,n - 1)
    if (d[edge[i].st] < d[edge[i].nd])
        swap(edge[i].st, edge[i].nd);
    while (q--){
        cin >> i >> u;
        int v = edge[i - 1].st;
        if (!anc(v,u)){
            cout << "escaped\n";
            continue;
        }
        if (dp[v] == oo){
            cout << "oo\n";
            continue;
        }

        cout << min (d[u] + jump(u,dep[u] - dep[v]),dp[u]) << "\n";
    }
    return 0;
}
/*



*/

Compilation message (stderr)

valley.cpp: In function 'void dfs1(int, int)':
valley.cpp:42:13: warning: unused variable 'w' [-Wunused-variable]
   42 |         int w = k.nd, v = k.st;
      |             ^

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