Submission #1209700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209700		DangKhoizzzz	Valley (BOI19_valley)	C++17	100 / 100	116 ms	51672 KiB

valley

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18;
const int maxn = 2e5 + 7;

bool mark[maxn];
int tin[maxn] , tout[maxn] , time_dfs = 0;
int N , Q , S , E , cnt[maxn] , dp[maxn] , jump[20][maxn] , mn[20][maxn] , dep[maxn];
vector <pii> g[maxn];
arr3 edge[maxn];

void dfs(int u , int p)
{
    tin[u] = ++time_dfs;
    dp[u] = INF;
    if(mark[u]) dp[u] = dep[u];

    for(pii e: g[u])
    {
        int v = e.fi;
        int w = e.se;
        if(v == p) continue;

        jump[0][v] = u;
        dep[v] = dep[u] + w;
        dfs(v , u);
        dp[u] = min(dp[v], dp[u]);
        mn[0][v] = min(dp[v] - 2*dep[v] , dp[u] - 2*dep[u]);
    }
    tout[u] = ++time_dfs;
}

void solve()
{
    cin >> N >> S >> Q >> E;
    for(int i = 1; i < N; i++)
    {
        cin >> edge[i][0] >> edge[i][1] >> edge[i][2];
        int u = edge[i][0] , v = edge[i][1] , w = edge[i][2];
        g[u].push_back({v , w});
        g[v].push_back({u , w});
    }
    for(int i = 1; i <= S; i++)
    {
        int u; cin >> u; mark[u] = 1;
    }
    dfs(E , E);
    dep[0] = -1;
    for(int j = 1; j < 19; j++)
    {
        for(int i = 1; i <= N; i++)
        {
            jump[j][i] = jump[j-1][jump[j-1][i]];
            mn[j][i] = min(mn[j-1][i] , mn[j-1][jump[j-1][i]]);
        }
    }
    while(Q--)
    {
        int I , R; cin >> I >> R;
        int u = edge[I][0] , v = edge[I][1];
        if(dep[u] < dep[v]) swap(u , v);

        if(tin[u] <= tin[R] && tout[R] <= tout[u])
        {
            int ans = dp[R] - dep[R];

            int h = dep[R];

            for(int i = 18; i >= 0; i--)
            {
                if(dep[jump[i][R]] >= dep[u])
                {
                    ans = min(ans , h + mn[i][R]);
                    R = jump[i][R];
                }
            }

            ans = min(ans , dp[R] - 2*dep[R] + h);

            if(ans > 1e16) cout << "oo" << '\n';
            else cout << ans << '\n';
        }
        else cout << "escaped" << '\n';
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //freopen("inp.txt", "r" , stdin);
    //freopen("out.txt", "w" , stdout);
    solve();
    return 0;
}

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