Submission #650764

#	Time	Username	Problem	Language	Result	Execution time	Memory
650764		iulia13	Valley (BOI19_valley)	C++14	100 / 100	493 ms	43308 KiB

valley

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int N = 1e5 + 5;
const int LG = 20;
const ll inf = 1e16;
struct ura{
    int x; ll c;
};
struct ura2{
    int x, y;
} edges[N];
vector <ura> g[N];
int n, s, q, e;
int h[N];
ll d[N];
int dad[N][LG];
ll dpmini[N][LG];
int shop[N];
ll mini[N];
void dfs(int nod)
{
    mini[nod] = inf;
    if (shop[nod])
        mini[nod] = d[nod];
    for (auto p : g[nod])
    {
        int x = p.x;
        ll c = p.c;
        if (x == dad[nod][0])
            continue;
        dad[x][0] = nod;
        h[x] = h[nod] + 1;
        d[x] = d[nod] + c;
        dfs(x);
        mini[nod] = min(mini[nod], mini[x]);
    }
}
void lifting()
{
    for (int j = 1; j <= 19; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            dad[i][j] = dad[dad[i][j - 1]][j - 1];
            dpmini[i][j] = min(dpmini[i][j - 1], dpmini[dad[i][j - 1]][j - 1]);
        }
    }
}
int main()
{
    cin >> n >> s >> q >> e;
    for (int i = 1; i < n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
        edges[i] = {a, b};
    }
    for (int i = 1; i <= s; i++)
    {
        int c;
        cin >> c;
        shop[c] = 1;
    }
    dfs(e);
    for (int i = 1; i <= n; i++)
    {
        dpmini[i][0] = inf;
        if (mini[i] != inf)
        dpmini[i][0] = mini[i] = mini[i] - 2 * d[i];

    }
    lifting();
    while(q--)
    {
        int ind, r;
        cin >> ind >> r;
        int a = edges[ind].x;
        int b = edges[ind].y;
        if (h[a] < h[b])
            swap(a, b);
        ///verific daca r e in subarb a
        int lg = 19; ll ans = inf;
        b = r;
        if (ind == 6)
            ind = 6;
        while (h[a] != h[b] && lg != -1)
        {
            if (h[dad[b][lg]] >= h[a])
            {
                ans = min(ans, dpmini[b][lg]);
                b = dad[b][lg];
            }
            lg--;
        }
        if (b != a)
        {
            cout << "escaped" << '\n';
            continue;
        }
        ans = min(ans, dpmini[b][0]);
        if (ans == inf)
            cout << "oo\n";
        else
            cout << ans + d[r] << '\n';
    }
    return 0;
}

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