Submission #927565

#	Time	Username	Problem	Language	Result	Execution time	Memory
927565		Muhammad_Aneeq	Valley (BOI19_valley)	C++17	59 / 100	3058 ms	43276 KiB

valley

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define int long long
int const N=1e5+10,LG=18;
int par[N][LG]={};
int pa[N]={},h[N]={},co[N]={};
vector<int>shops;
int n,s,q,e;
vector<int>f;
vector<pair<int,int>>nei[N]={};
set<pair<int,int>>s1;
void precomp()
{
    for (int i=1;i<=n;i++)
        par[i][0]=pa[i];
    for (auto [h,i]:s1)
        for (int j=1;j<LG;j++)
            if (par[i][j-1]!=0)
                par[i][j]=par[par[i][j-1]][j-1];
}
void lift(int d,int& x)
{
    for (int i=0;i<LG;i++)
    {
        if ((1<<i)&d)
            x=par[x][i];
    }
}
int LCA(int u,int v)
{
    if (h[u]<h[v])
        swap(u,v);
    lift(h[u]-h[v],u);
    if (u==v)
        return u;
    for (int i=LG-1;i>=0;i--)
    {
        if (par[u][i]==par[v][i])
            continue;
        u=par[u][i];
        v=par[v][i];
    }
    return par[u][0];
}
void dfs(int n,int m=-1)
{   
    s1.insert({h[n],n});
    for (auto [i,w]:nei[n])
    {
        if (i==m)
            continue;
        pa[i]=n;
        h[i]=h[n]+1;
        co[i]=co[n]+w;
        dfs(i,n);
    }
}
inline void solve()
{
    cin>>n>>s>>q>>e;
    vector<pair<int,int>>ed;
    for (int i=1;i<n;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        nei[u].push_back({v,w});
        nei[v].push_back({u,w});
        ed.push_back({u,v});
    }
    dfs(1);
    precomp();
    while (s--)
    {
        int x;
        cin>>x;
        shops.push_back(x);
    }
    sort(begin(shops),end(shops));
    while (q--)
    {
        int i,r;
        cin>>i>>r;
        i--;
        int u=ed[i].first,v=ed[i].second;
        int z=LCA(r,e);
        bool w=1;
        if (((LCA(r,v)==v&&LCA(v,z)==z)&&(LCA(r,u)==u&&LCA(u,z)==z))||((LCA(e,v)==v&&LCA(v,z)==z)&&(LCA(e,u)==u&&LCA(u,z)==z)))
            w=0;
        if (w)
        {
            cout<<"escaped\n";
            continue;
        }
        auto y=lower_bound(begin(shops),end(shops),r);
        if (y!=shops.end()&&*y==r)
        {
            cout<<0<<endl;continue;
        }
        int ans=1e15+10;
        for (auto j:shops)
        {
            int z=LCA(r,j);
            bool w=1;
            if (((LCA(r,v)==v&&LCA(v,z)==z)&&(LCA(r,u)==u&&LCA(u,z)==z))||((LCA(j,v)==v&&LCA(v,z)==z)&&(LCA(j,u)==u&&LCA(u,z)==z)))
                w=0;
            if (w)
                ans=min(ans,co[r]+co[j]-2*co[z]);
        }
        if (ans==1e15+10)
            cout<<"oo\n";
        else
            cout<<ans<<endl;
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        solve();
}

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