Submission #834366

#	Time	Username	Problem	Language	Result	Execution time	Memory
834366		TheSahib	Valley (BOI19_valley)	C++14	100 / 100	351 ms	58224 KiB

valley

#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>

using namespace std;

const ll oo = 1e18;
const int MAX = 1e5 + 5;
const int LOGMAX = 17;

struct edge{
    int a, b, w;
};

edge edges[MAX];
vector<int> g[MAX];

bool shop[MAX];
ll dp[MAX];
array<ll, 3> par[LOGMAX][MAX];

int t = 0;
int timeIn[MAX], timeOut[MAX];

void dfs1(int node, int p){
    par[0][node] = {p, 0, 0};
    dp[node] = oo;
    if(shop[node]) dp[node] = 0;

    timeIn[node] = ++t;
    for(int i:g[node]){
        edge& e = edges[i];
        if(e.a != node){
            swap(e.a, e.b);
        }
        if(e.b == p){
            swap(e.a, e.b);
            continue;
        }
        dfs1(e.b, node);
        par[0][e.b][1] = e.w;
        dp[node] = min(dp[node], dp[e.b] + e.w);
    }
    par[0][node][2] = dp[node];
    timeOut[node] = ++t;
}
bool isAncestor(int a, int b){
    return timeIn[a] <= timeIn[b] && timeOut[a] >= timeOut[b];
}

ll lift(int node, int p){
    ll ans = oo;
    ll d = 0;
    for (int j = LOGMAX - 1; j >= 0; --j)
    {
        int a = par[j][node][0];
        if(isAncestor(a, p)) continue;
        ans = min(ans, par[j][node][2] + d);
        d += par[j][node][1];
        node = a;
    }
    ans = min(ans, par[0][node][2] + d);
    return ans;
}

int n, s, q, r;

int main()
{
    cin >> n >> s >> q >> r;
    for (int i = 1; i <= n - 1; i++)
    {
        edge e;
        cin >> e.a >> e.b >> e.w;
        edges[i] = e;
        g[e.a].push_back(i);
        g[e.b].push_back(i);
    }
    for (int i = 0; i < s; i++)
    {
        int a; cin >> a;
        shop[a] = 1;
    }
    dfs1(r, r);
    for (int j = 1; j < LOGMAX; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            int m = par[j - 1][i][0];
            par[j][i][0] = par[j - 1][m][0];
            par[j][i][1] = par[j - 1][i][1] + par[j - 1][m][1];
            par[j][i][2] = min(par[j - 1][i][2], par[j - 1][i][1] + par[j - 1][m][2]);
        }     
    }
    
    while(q--){
        int a, b; cin >> a >> b;
        if(!isAncestor(edges[a].b, b)){
            cout << "escaped\n";
            continue;
        }
        ll ans = lift(b, edges[a].a);
        if(ans == oo){
            cout << "oo\n";
        }
        else{
            cout << ans << '\n';
        }
    }
}

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