Submission #1271815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271815		k12_khoi	Valley (BOI19_valley)	C++17	100 / 100	107 ms	43200 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll,int>
#define X first
#define Y second

const int N=1e5+5;
const int K=22;
const ll oo=(long double)1e18+1;

int n,request,s,e,h,x,y,z,save,temp,timer; ll res;
int a[N],b[N],in[N],out[N],H[N],p[N][K]; ll dist[N],mi[N][K];
bool HasShop[N];
vector <pii> adj[N];

bool yInSubtreex(int x,int y)
{
    return in[x]<=in[y] and out[y]<=out[x];
}

void pre_dfs(int u,int par)
{
    in[u]=++timer;


    if (HasShop[u]) mi[u][0]=dist[u];
    else mi[u][0]=oo;

    for (pii v:adj[u])
    if (v.Y!=par)
    {
        H[v.Y]=H[u]+1;
        dist[v.Y]=dist[u]+v.X;
        p[v.Y][0]=u;

        pre_dfs(v.Y,u);

        mi[u][0]=min(mi[u][0],mi[v.Y][0]+2*dist[v.Y]);
    }

    if (mi[u][0]!=oo) mi[u][0]-=2*dist[u];


    out[u]=timer;
}

ll lift_getmin(int x,int k)
{
    ll ans_mi=oo;

    for (int j=0;j<=h;j++)
    if (k&(1<<j))
    {
        ans_mi=min(ans_mi,mi[x][j]);
        x=p[x][j];
    }

    return ans_mi;
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> s >> request >> e;
    for (int i=1;i<n;i++)
    {
        cin >> x >> y >> z;
        adj[x].push_back(make_pair(z,y));
        adj[y].push_back(make_pair(z,x));

        a[i]=x;
        b[i]=y;
    }

    for (int i=1;i<=s;i++)
    {
        cin >> x;
        HasShop[x]=true;
    }
    H[e]=1;
    dist[e]=0;
    timer=0;
    pre_dfs(e,-1);

    for (int i=1;i<n;i++)
    if (H[a[i]]>H[b[i]]) swap(a[i],b[i]);


    h=31-__builtin_clz(n);

    for (int j=1;j<=h;j++)
    for (int i=1;i<=n;i++)
    {
        p[i][j]=p[p[i][j-1]][j-1];
        mi[i][j]=min(mi[i][j-1],mi[p[i][j-1]][j-1]);
    }


    while (request--)
    {
        cin >> save >> y;
        x=b[save];


        if (yInSubtreex(x,y))
        {
            temp=H[y]-H[x];

            res=lift_getmin(y,temp+1);

            if (res==oo) cout << "oo" << '\n';
            else cout << res+dist[y] << '\n';
        }
        else cout << "escaped" << '\n';
    }
}

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