Submission #528756

#	Time	Username	Problem	Language	Result	Execution time	Memory
528756		kderylo	Valley (BOI19_valley)	C++17	100 / 100	211 ms	45036 KiB

valley

#include <iostream>
#include <vector>
using namespace std;
const int stala=1e5+10;
vector<int>wektor[stala];
vector<long long>stopien[stala];
bool czy_sklep[stala];
long long dp[stala];
int ojciec[stala];
int krawedzie[stala][2];
int t[stala][2];
long long odl_ojciec[stala];
long long glebokosc[stala];
int gl[stala];
int ancestor[stala][17];
long long ans[stala][17];
int ti=0;
void dfs(int k,int p,long long odl)
{
    ojciec[k]=p;
    odl_ojciec[k]=odl;
    ti++;
    t[k][0]=ti;
    if(czy_sklep[k]==0)
    {
        dp[k]=1e18;
    }
    for(int i=0;i<(int)wektor[k].size();i++)
    {
        if(wektor[k][i]!=p)
        {
            glebokosc[wektor[k][i]]=glebokosc[k]+stopien[k][i];
            gl[wektor[k][i]]=gl[k]+1;
            dfs(wektor[k][i],k,stopien[k][i]);
            dp[k]=min(dp[k],dp[wektor[k][i]]+stopien[k][i]);
        }
    }
    t[k][1]=ti;
}
void ustaw_lca(int ile)
{
    for(int i=1;i<=ile;i++)
    {
        ancestor[i][0]=ojciec[i];
        ans[i][0]=dp[i];
    }
    for(int i=1;i<=16;i++)
    {
        for(int j=1;j<=ile;j++)
        {
            ancestor[j][i]=ancestor[ancestor[j][i-1]][i-1];
            int w=ancestor[j][i-1];
            ans[j][i]=min(ans[j][i-1],ans[w][i-1]+glebokosc[j]-glebokosc[w]);
        }
    }
}
long long znajdz(int ile_w_gore,int start)
{
    long long minimum=1e18;
    int index=start;
    for(int i=16;i>=0;i--)
    {
        if((1<<i)<=ile_w_gore)
        {
            ile_w_gore-=(1<<i);
            minimum=min(minimum,ans[index][i]+glebokosc[start]-glebokosc[index]);
            index=ancestor[index][i];
        }
    }
    return minimum;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ile,sklepy,zap,start;
    cin>>ile>>sklepy>>zap>>start;
    for(int i=1;i<=ile-1;i++)
    {
        int a,b;
        long long c;
        cin>>a>>b>>c;
        krawedzie[i][0]=a;
        krawedzie[i][1]=b;
        wektor[a].push_back(b);
        wektor[b].push_back(a);
        stopien[a].push_back(c);
        stopien[b].push_back(c);
    }
    for(int i=1;i<=sklepy;i++)
    {
        int a;
        cin>>a;
        czy_sklep[a]=1;
    }
    gl[start]=1;
    dfs(start,0,0);
    ustaw_lca(ile);
    for(int i=1;i<=zap;i++)
    {
        int nr,wierzcholek,w;
        cin>>nr>>wierzcholek;
        if(ojciec[krawedzie[nr][0]]==krawedzie[nr][1])
        {
            w=krawedzie[nr][0];
        }
        else
        {
            w=krawedzie[nr][1];
        }
        if(t[w][0]<=t[wierzcholek][0]&&t[wierzcholek][0]<=t[w][1])
        {
            long long wyn=znajdz(gl[wierzcholek]-gl[w]+1,wierzcholek);
            if(wyn==1e18)
            {
                cout<<"oo"<<"\n";
            }
            else
            {
                cout<<wyn<<"\n";
            }
        }
        else
        {
            cout<<"escaped"<<"\n";
        }
    }

    return 0;
}

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