Submission #560082

#	Time	Username	Problem	Language	Result	Execution time	Memory
560082		messiuuuuu	Valley (BOI19_valley)	C++14	0 / 100	165 ms	33236 KiB

valley

#include <bits/stdc++.h>
#define task "VALLEY"
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 1e5 + 5;
const ll INF = 1e18 + 5;
const int LOGN = 19;

int n, s, q, e;
vector<pair<int, int>> Adj[MAXN];
bool ishop[MAXN];
struct TEdge
{
    int u, v, w;
}es[MAXN];

void Input()
{
    cin >> n >> s >> q >> e;
    for (int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        es[i] = {u, v, w};
        Adj[u].pb({v, w});
        Adj[v].pb({u, w});
    }
    for (int i = 1; i <= s; i++)
    {
        int c;
        cin >> c;
        ishop[c] = 1;
    }
}

ll dp[MAXN];
int P[MAXN][LOGN];
ll M[MAXN][LOGN], d[MAXN];
int deg[MAXN];

void DFS(int u, int par)
{
    if (!ishop[u])
        dp[u] = INF;
    for (auto v : Adj[u])
    {
        if (v.fi == par)
            continue;
        d[v.fi] = v.se + d[u];
        P[v.fi][0] = u;
        deg[v.fi] = deg[u] + 1;
        DFS(v.fi, u);
        dp[u] = min(dp[u], dp[v.fi] + v.se);
    }
}

void DFS2(int u, int par)
{
    for (auto v : Adj[u])
    {
        if (v.fi != par)
        {
            M[v.fi][0] = dp[u] - d[u];
            DFS2(v.fi, u);
        }
    }
}

bool LCAdinh(int u, int v)
{
    for (int i = LOGN - 1; i >= 0; i--)
    {
        if (deg[P[u][i]] >= deg[v])
            u = P[u][i];
    }
    return u == v;
}

ll LCAcanh(int u, int v)
{
    ll res = dp[u];
    for (int i = LOGN - 1; i >= 0; i--)
    {
        if (deg[P[u][i]] >= deg[v])
        {
            res = min(res, M[u][i]);
            u = P[u][i];
        }
    }
    res = min(res, dp[v]);
    return res;
}

void Solve()
{
    deg[e] = 1;
    DFS(e, 0);
    DFS2(e, 0);
    for (int i = 1; i < LOGN; i++)
        for (int j = 1; j <= n; j++)
        {
            P[j][i] = P[P[j][i - 1]][i - 1];
            M[j][i] = min(M[j][i - 1], M[P[j][i - 1]][i - 1]);
        }
    while (q-- > 0)
    {
        int id, r;
        cin >> id >> r;
        if (P[es[id].u][0] == es[id].v)
            swap(es[id].u, es[id].v);
        if (!LCAdinh(r, es[id].v))
        {
             cout << "escaped\n";
             continue;
        }
        ll ans = LCAcanh(r, es[id].v);
        if (ans == INF)
            cout << "oo\n";
        else
            cout << ans + d[r] << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen(task".INP" , "r" , stdin);
    //freopen(taskname".OUT" , "w" , stdout);
    Input();
    Solve();
    return 0;
}

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