oj.uz

Submission #203349

# Submission time Handle Problem Language Result Execution time Memory
203349 2020-02-20T09:44:36 Z mdn2002 Valley (BOI19_valley) C++14
23 / 100
 713 ms 39408 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 37752 KB Output is correct
2 Correct 619 ms 37624 KB Output is correct
3 Correct 593 ms 37240 KB Output is correct
4 Correct 624 ms 38392 KB Output is correct
5 Correct 640 ms 38560 KB Output is correct
6 Correct 713 ms 39408 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -