Submission #942168

#	Time	Username	Problem	Language	Result	Execution time	Memory
942168		maxFedorchuk	Valley (BOI19_valley)	C++17	100 / 100	172 ms	91728 KiB

valley

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

const long long MX=2e5+10;
const long long INF=1e18;
const long long lg=20;

vector < pair < long long , long long > > mas[MX];
long long a[MX],b[MX],god[MX];

long long h[MX],d[MX];

long long tin[MX],tou[MX],timer=0;
long long mans[lg][MX],lca[lg][MX];

void DFS(int zar)
{
    timer++;
    tin[zar]=timer;

    for(int i=1;i<lg;i++)
    {
        lca[i][zar]=lca[i-1][lca[i-1][zar]];
    }

    d[zar]=(!god[zar])*INF;
    for(auto [u,w]:mas[zar])
    {
        if(u!=lca[0][zar])
        {
            h[u]=h[zar]+w;
            lca[0][u]=zar;

            DFS(u);

            d[zar]=min(d[zar],d[u]+w);
        }
    }

    mans[0][zar]=d[zar]-h[zar];

    timer++;
    tou[zar]=timer;
}

bool prd(long long pr,long long s)
{
    return (tin[pr]<=tin[s] && tou[s]<=tou[pr]);
}
void fun(long long in,long long zn)
{
    if(!prd(b[in],zn))
    {
        cout<<"escaped\n";
        return;
    }

    if(d[b[in]]==INF)
    {
        cout<<"oo\n";
        return;
    }

    long long ans=mans[0][b[in]],zar=zn;
    for(int i=lg-1;i>=0;i--)
    {
        if(prd(b[in],lca[i][zar]))
        {
            ans=min(ans,mans[i][zar]);
            zar=lca[i][zar];
        }
    }
    cout<<ans+h[zn]<<"\n";
}

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

    long long n,s,q,e;
    cin>>n>>s>>q>>e;

    for(long long i=1;i<n;i++)
    {
        long long w;
        cin>>a[i]>>b[i]>>w;

        mas[a[i]].push_back({b[i],w});
        mas[b[i]].push_back({a[i],w});
    }

    for(long long i=1;i<=s;i++)
    {
        long long o;
        cin>>o;
        god[o]=1;
    }

    lca[0][e]=e;
    DFS(e);

    for(long long i=1;i<n;i++)
    {
        if(tin[a[i]]>tin[b[i]])
        {
            swap(a[i],b[i]);
        }
    }

    for(long long j=1;j<lg;j++)
    {
        for(long long i=1;i<=n;i++)
        {
            mans[j][i]=min(mans[j-1][i],mans[j-1][lca[j-1][i]]);
        }
    }

    while(q--)
    {
        long long id,zn;
        cin>>id>>zn;

        fun(id,zn);
    }
    
    return 0;
}

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