Submission #589329

#	Time	Username	Problem	Language	Result	Execution time	Memory
589329		danikoynov	Valley (BOI19_valley)	C++14	100 / 100	187 ms	52532 KiB

valley

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10, maxlog = 20;
const ll inf = 1e18;
int n, s, q, e;
bool shop[maxn];

vector < pair < int, ll > > g[maxn];
int in[maxn], out[maxn], timer, lvl[maxn];
ll dp[maxn], cl[maxn], depth[maxn], jump[maxn][maxlog], mx[maxn][maxlog];
/// + depth[u] - 2 * depth[v]
void dfs(int v, int p)
{
    in[v] = ++ timer;
    cl[v] = inf;
    for (pair < int, ll > nb : g[v])
    {
        int u = nb.first;
        if (u == p)
            continue;
        lvl[u] = lvl[v] + 1;
        depth[u] = depth[v] + nb.second;
            dfs(u, v);
            if (cl[u] < cl[v])
                cl[v] = cl[u];

    }
    if (shop[v])
        cl[v] = depth[v];
    dp[v] = cl[v] - 2 * depth[v];
    jump[v][0] = p;
    out[v] = timer;
}

bool in_subtree(int v, int u)
{
    if (in[v] <= in[u] && out[v] >= out[u])
        return true;
    return false;
}

ll make_jump(int v, int len)
{
    ll ans = dp[v];
    for (int bit = maxlog - 1; bit >= 0; bit --)
    {
        if ((len & (1 << bit)) > 0)
        {
            ans = min(ans, mx[v][bit]), v = jump[v][bit];
        }
    }
    return ans;
}
pair < int, int > edge[maxn];

void solve()
{
    cin >> n >> s >> q >> e;
    for (int i = 1; i < n; i ++)
    {
        int v, u;
        ll w;
        cin >> v >> u >> w;
        g[v].push_back({u, w});
        g[u].push_back({v, w});
        edge[i] = {v, u};
    }

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

    dp[0] = inf;
    dfs(e, 0);

    for (int j = 0; j < maxlog; j ++)
        mx[0][j] = inf;

        for (int i = 1; i <= n; i ++)
            mx[i][0] = dp[jump[i][0]];
    for (int j = 1; j < maxlog; j ++)
    {
        for (int i = 1; i <= n; i ++)
        {
            jump[i][j] = jump[jump[i][j - 1]][j - 1];
            mx[i][j] = min(mx[i][j - 1], mx[jump[i][j - 1]][j - 1]);
        }
    }

    for (int i = 1; i < n; i ++)
        if (lvl[edge[i].first] > lvl[edge[i].second])
        swap(edge[i].first, edge[i].second);

    for (int i = 1; i <= q; i ++)
    {
        int id, v;
        cin >> id >> v;
        if (in_subtree(edge[id].second, v))
        {
            int len = lvl[v] - lvl[edge[id].second];
            ll ans = make_jump(v, len) + depth[v];
            if (cl[edge[id].second] == inf)
                cout << "oo" << endl;
            else
            cout << ans << endl;
        }
        else
        cout << "escaped" << endl;

    }

}

int main()
{
    speed();
    solve();
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void solve()':
valley.cpp:98:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   98 |     for (int j = 0; j < maxlog; j ++)
      |     ^~~
valley.cpp:101:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  101 |         for (int i = 1; i <= n; i ++)
      |         ^~~

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