Submission #753182

#	Time	Username	Problem	Language	Result	Execution time	Memory
753182		amin	Valley (BOI19_valley)	C++14	100 / 100	429 ms	57392 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll p[21][100000],mi[21][100000];
ll ans=1000000000;

int get(int x,int y)
{
    if(y<0)
        return 0;
    int u=1;
    int k=0;
//cout<<x<<' ';
    while(k<=20&&y>0)
    {
        if((u&y)==u)
        {
            ans=min(ans,mi[k][x]);
            x=p[k][x];
           // cout<<x<<' ';
        //    cout<<mi[k][x]<<endl;

        }

        u*=2;
        k++;
    }
   // cout<<endl;
    return x;
}
vector<ll>v[100000];
vector<ll>w[100000];
ll m[100000];
ll val[100000];
ll dist[100000];
ll u[100000];
void dfs(int in,int pa)
{
    val[in]=1e18;

    for(int i=0;i<v[in].size();i++)
    {
        if(v[in][i]==pa)
        {
            continue ;
        }
        p[0][v[in][i]]=in;
        dist[v[in][i]]=dist[in]+w[in][i];
        u[v[in][i]]=u[in]+1;
        dfs(v[in][i],in);
        val[in]=min(val[in],val[v[in][i]]+w[in][i]);


    }
    if(m[in]==1)
        val[in]=0;


}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  //  freopen("balancing.in","r",stdin);
   // freopen("balancing.out","w",stdout);
ll n,s,q,e;
cin>>n>>s>>q>>e;
ll a[n],b[n],c[n];
e--;
for(int i=0;i<n-1;i++)
{
    cin>>a[i]>>b[i]>>c[i];
    a[i]--;
    b[i]--;
    v[a[i]].push_back(b[i]);
    w[a[i]].push_back(c[i]);
    v[b[i]].push_back(a[i]);
    w[b[i]].push_back(c[i]);

}
for(int i=0;i<s;i++)
{
    int z;
    cin>>z;
    z--;
    m[z]=1;
}
dfs(e,e);
p[0][e]=e;
for(int i=0;i<n;i++)
{
    val[i]-=dist[i];
    mi[0][i]=val[i];
    //cout<<dist[i]<<' ';
}
//cout<<endl;
for(int i=1;i<20;i++)
{
    for(int y=0;y<n;y++)
    {
        p[i][y]=p[i-1][p[i-1][y]];
        mi[i][y]=min(mi[i-1][y],mi[i-1][p[i-1][y]]);
        /*if(i<4)
        {
            cout<<mi[i][y]<<' ';
        }*/
      /*  if(i==1)
            cout<<p[0][y]<<' ';*/
    }
    /*if(i<4)
    cout<<endl;*/
}
while(q--)
{
    int x,y;
    cin>>x>>y;
    swap(x,y);
 //   cout<<111<<endl;
    y--;
    x--;
    int st,en;
        st=b[y];
    en=a[y];
if(dist[a[y]]<dist[b[y]])
{
    st=a[y];
    en=b[y];
}
//cout<<222<<endl;
ll di=u[x]-u[en];
ans=1000000000000000000;

int c=get(x,di);

//cout<<c<<endl;
//cout<<333<<endl;
//cout<<ans<<' ';
if(c!=en||di<0)
{
    cout<<"escaped"<<endl;
    continue;
}
ans=1000000000000000000;
get(x,di+1);
//cout<<ans<<' ';
if(min(val[x]+dist[x],dist[x]+ans)<100000000000000000)
cout<<min(val[x]+dist[x],dist[x]+ans)<<endl;
else
    cout<<"oo"<<endl;

}
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0;i<v[in].size();i++)
      |                 ~^~~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:124:9: warning: variable 'st' set but not used [-Wunused-but-set-variable]
  124 |     int st,en;
      |         ^~

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