Submission #594059

#	Time	Username	Problem	Language	Result	Execution time	Memory
594059		Hanksburger	Valley (BOI19_valley)	C++17	100 / 100	190 ms	40524 KiB

valley

#include <bits/stdc++.h>
using namespace std;
int par[100005][17], dep[100005], l[100005], r[100005];
vector<pair<int, long long> > adj[100005];
long long dp[100005][17], dis[100005];
pair<int, int> edge[100005];
bool shop[100005];
vector<int> vec;
void dfs(int u, int p)
{
    vec.push_back(u);
    if (shop[u])
        dp[u][0]=dis[u];
    else
        dp[u][0]=2e18;
    par[u][0]=p;
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first;
        long long w=adj[u][i].second;
        if (v!=p)
        {
            dis[v]=dis[u]+w;
            dep[v]=dep[u]+1;
            dfs(v, u);
            dp[u][0]=min(dp[u][0], dp[v][0]);
        }
    }
    vec.push_back(u);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, s, q, e;
    cin >> n >> s >> q >> e;
    for (int i=1; i<n; i++)
    {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        edge[i]={u, v};
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int i=1; i<=s; i++)
    {
        int u;
        cin >> u;
        shop[u]=1;
    }
    dfs(e, e);
    for (int i=1; i<=n; i++)
        dp[i][0]-=dis[i]*2;
    for (int i=1; i<=16; i++)
    {
        for (int j=1; j<=n; j++)
        {
            dp[j][i]=min(dp[j][i-1], dp[par[j][i-1]][i-1]);
            par[j][i]=par[par[j][i-1]][i-1];
        }
    }
    for (int i=0; i<n*2; i++)
        if (!l[vec[i]])
            l[vec[i]]=i+1;
    for (int i=n*2-1; i>=0; i--)
        if (!r[vec[i]])
            r[vec[i]]=i+1;
    for (int i=1; i<=q; i++)
    {
        int x, y;
        cin >> x >> y;
        if (dep[edge[x].first]>dep[edge[x].second])
            x=edge[x].first;
        else
            x=edge[x].second;
        if (l[x]<=l[y] && r[y]<=r[x])
        {
            int d=dep[y]-dep[x]+1, cur=y;
            long long mn=2e18;
            for (int i=0; i<=16; i++)
            {
                if (d&(1<<i))
                {
                    mn=min(mn, dp[cur][i]);
                    cur=par[cur][i];
                }
            }
            if (mn<1e18)
                cout << mn+dis[y] << '\n';
            else
                cout << "oo\n";
        }
        else
            cout << "escaped\n";
    }
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i=0; i<adj[u].size(); i++)
      |                   ~^~~~~~~~~~~~~~

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