Submission #203349

#	Time	Username	Problem	Language	Result	Execution time	Memory
203349		mdn2002	Valley (BOI19_valley)	C++14	23 / 100	713 ms	39408 KiB

valley

#include<bits/stdc++.h>
using namespace std;
long long n,s,q,e,st[100005][30],dp[100005],fo[100005],to[100005],sp[100005];
vector<pair<int,int> >gr[100005];
void dfs(int x,int p,int dis)
{
    dp[x]=dp[p]+1;
    st[x][0]=p;
    for(int i=0;i<gr[x].size();i++)
    {
        int u=gr[x][i].first,w=gr[x][i].second;
        if(u==p)continue;
        dfs(u,x,dis+w);
    }
}
bool ck(int x,int fr)
{
    int dif=dp[x]-dp[fr];
    if(dif<0)return 0;
    for(int i=0;i<=21;i++)
    {
        if((dif&(1<<i)))x=st[x][i];
    }
    if(x==fr)return 1;
    else return 0;
}
int main()
{
    cin>>n>>s>>q>>e;
    for(int i=0;i<n-1;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        fo[i]=x,to[i]=y;
        gr[x].push_back({y,w});
        gr[y].push_back({x,w});
    }
    dfs(e,0,0);
    for(int i=1;i<=25;i++)
    {
        for(int j=1;j<=n;j++)st[j][i]=st[st[j][i-1]][i-1];
    }
    for(int i=0;i<s;i++)
    {
        int x;
        cin>>x;
        sp[x]++;
    }
    while(q--)
    {
        int a,x;
        cin>>a>>x;
        a--;
        int fr;
        if(dp[fo[a]]<dp[to[a]])fr=to[a];
        else fr=fo[a];
        if(ck(x,fr))cout<<0<<endl;
        else cout<<"escaped"<<endl;
    }
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(int, int, int)':
valley.cpp:9:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gr[x].size();i++)
                 ~^~~~~~~~~~~~~

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