Submission #363162

#	Time	Username	Problem	Language	Result	Execution time	Memory
363162		ngpin04	Valley (BOI19_valley)	C++14	100 / 100	250 ms	42092 KiB

valley

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 1e5 + 5;
const long long oo = 1e18;

vector <pair <int, int>> adj[N];

pair <int, int> edge[N];

long long dp[20][N];
long long mindis[N];
long long dis[N];
long long val[N];

int lca[20][N];
int h[N];
int n,s,q,t;

bool store[N];

void dfs(int u, int p)
{
    lca[0][u] = p;

    mindis[u] = (store[u]) ? dis[u] : oo;

    for (pair <int, int> to : adj[u])
    {
        int v = to.fi;
        int w = to.se;
        if (v == p)
            continue;
        h[v] = h[u] + 1;
        dis[v] = dis[u] + w;
        dfs(v, u);
        mindis[u] = min(mindis[u], mindis[v]);
    }
    val[u] = mindis[u] - 2 * dis[u];
}

void build()
{
    for (int i = 1; i <= n; i++)
    {
        int p = lca[0][i];
        dp[0][i] = (p < 0) ? oo : val[p];
    }

    for (int j = 1; j < 20; j++)
    for (int i = 1; i <= n; i++)
    {
        int p = lca[j - 1][i];
        if (p < 0)
            lca[j][i] = p, dp[j][i] = oo;
        else
            lca[j][i] = lca[j - 1][p], dp[j][i] = min(dp[j - 1][p], dp[j - 1][i]);
    }
}

pair <long long, int> jump(int u, int step)
{
    if (step < 0)
        return mp(oo, -1);

    long long res = val[u];
    for (int i = 0; i < 20; i++) if ((step >> i) & 1)
    {
        res = min(res, dp[i][u]);
        u = lca[i][u];
    }
    return mp(res, u);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.inp","r",stdin);
    cin >> n >> s >> q >> t;
    for (int i = 1; i < n; i++)
    {
        int u,v,w;
        cin >> u >> v >> w;

        adj[u].push_back(mp(v, w));
        adj[v].push_back(mp(u, w));

        edge[i] = mp(u, v);
    }

    for (int i = 1; i <= s; i++)
    {
        int x;
        cin >> x;
        store[x] = true;
    }

    dfs(t, -1);

    build();

    while (q--)
    {
        int id,cur;
        cin >> id >> cur;
        int u = edge[id].fi;
        int v = edge[id].se;
        if (h[u] > h[v])
            swap(u, v);

        pair <long long, int> res = jump(cur, h[cur] - h[v]);
        if (res.se != v)
            cout << "escaped\n";
        else if (res.fi > (long long) 1e15)
            cout << "oo\n";
        else
            cout << res.fi + dis[cur] << "\n";
    }
    return 0;
}

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