oj.uz

Submission #203351

# Submission time Handle Problem Language Result Execution time Memory
203351 2020-02-20T10:02:55 Z mdn2002 Valley (BOI19_valley) C++14
0 / 100
 644 ms 59232 KB 
#include<bits/stdc++.h>
using namespace std;
long long n,s,q,e,st[100005][30],mn[100005][30],os[100005],di[100005],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;
    di[x]=dis;
    os[x]=1e18;
    if(sp[x])os[x]=dis;
    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);
        os[x]=min(os[x],os[u]);
    }
    mn[x][0]=os[x]-(2*dis);
}
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});
    }
    for(int i=0;i<s;i++)
    {
        int x;
        cin>>x;
        sp[x]++;
    }
    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];
            mn[j][i]=min(mn[st[j][i-1]][i-1],mn[j][i-1]);
        }
    }
    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)==0)
        {
            cout<<"escaped"<<endl;
            continue;
        }
        long long ans=1e18,nod=x;
        for(int i=21;i>=0;i--)
        {
            if(dp[st[nod][i]]>=dp[fr])
            {
                ans=min(ans,mn[nod][i]+di[x]);
                nod=st[nod][i];
            }
        }
        ans=min(ans,mn[fr][0]+di[x]);
        if(ans>1e15)cout<<"oo"<<endl;
        else cout<<ans<<endl;
    }
}

Compilation message

valley.cpp: In function 'void dfs(int, int, int)':
valley.cpp:12: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 Correct 32 ms 2808 KB Output is correct
2 Incorrect 36 ms 2932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2808 KB Output is correct
2 Incorrect 36 ms 2932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

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

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2808 KB Output is correct
2 Incorrect 36 ms 2932 KB Output isn't correct
3 Halted 0 ms 0 KB -