Submission #1146094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146094		LeonidCuk	Valley (BOI19_valley)	C++20	100 / 100	425 ms	103724 KiB

valley

#include <bits/stdc++.h>
using namespace std;
vector<long long int>lcasum[100000],lcamin[100000],lca[100000],d(100000),v(100000);
vector<pair<int,int>>g[100000],edge;
bool vis[100000]={0};
long long Maxn=1e15;
void dfs1(int a,int b)
{
    v[a]=Maxn;
    if(vis[a])v[a]=0;
    for(auto i:g[a])
    {
        if(i.first!=b)
        {
            d[i.first]=d[a]+1;
            dfs1(i.first,a);
            v[a]=min(v[a],v[i.first]+i.second);
        }
    }
}
void dfs(int a,int b,long long int sum)
{
    lca[a].push_back(b);
    lcasum[a].push_back(sum);
    lcamin[a].push_back(v[a]);
    for(int i=1;i<20;i++)
    {
        lca[a].push_back(lca[lca[a][i-1]][i-1]);
        lcasum[a].push_back(lcasum[a][i-1]+lcasum[lca[a][i-1]][i-1]);
        lcamin[a].push_back(min(lcamin[a][i-1],lcasum[a][i-1]+lcamin[lca[a][i-1]][i-1]));
    }
    for(auto i:g[a])
    {
        if(i.first!=b)
        {
            dfs(i.first,a,i.second);
        }
    }
}
long long int lcaq(int a,int b)
{
    if(d[a]<d[b])return -1;
    long long int sum=0,res=Maxn;
    for(int i=19;i>=0;i--)
    {
        if(d[lca[a][i]]>=d[b])
        {
            res=min(res,sum+lcamin[a][i]);
            sum+=lcasum[a][i];
            a=lca[a][i];
        }
    }
    if(a!=b)return -1;
    return min(res,sum+lcamin[a][0]);
}
int main()
{
    int n,m,q,k,a,b,c;
    cin>>n>>m>>q>>k;
    k--;
    for(int i=0;i<n-1;i++)
    {
        cin>>a>>b>>c;
        g[a-1].push_back({b-1,c});
        g[b-1].push_back({a-1,c});
        edge.push_back({a-1,b-1});
    }
    for(int i=0;i<m;i++)
    {
        cin>>a;
        vis[a-1]=1;
    }
    dfs1(k,k);
    dfs(k,k,0);
    for(int i=0;i<q;i++)
    {
        cin>>a>>b;
        if(d[edge[a-1].first]<d[edge[a-1].second])a=edge[a-1].second;
        else a=edge[a-1].first;
        long long int res=lcaq(b-1,a);
        if(res==-1)cout<<"escaped";
        else if(res==Maxn)cout<<"oo";
        else cout<<res;
        cout<<"\n";
    }
    return 0;
}

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