oj.uz

답안 #203355

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
203355 2020-02-20T10:06:07 Z mdn2002 Valley (BOI19_valley) C++14
100 / 100
 807 ms 66552 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,long long dis)
{
    dp[x]=dp[p]+1;
    st[x][0]=p;
    di[x]=dis;
    os[x]=1e16;
    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;
        if(sp[x])ans=0;
        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, long long 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
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 2808 KB Output is correct
2 Correct 36 ms 2936 KB Output is correct
3 Correct 33 ms 2936 KB Output is correct
4 Correct 32 ms 2936 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 2808 KB Output is correct
2 Correct 36 ms 2936 KB Output is correct
3 Correct 33 ms 2936 KB Output is correct
4 Correct 32 ms 2936 KB Output is correct
5 Correct 11 ms 3320 KB Output is correct
6 Correct 11 ms 3320 KB Output is correct
7 Correct 11 ms 3320 KB Output is correct
8 Correct 11 ms 3320 KB Output is correct
9 Correct 11 ms 3320 KB Output is correct
10 Correct 11 ms 3320 KB Output is correct
11 Correct 11 ms 3320 KB Output is correct
12 Correct 11 ms 3320 KB Output is correct
13 Correct 11 ms 3320 KB Output is correct
14 Correct 11 ms 3320 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 645 ms 58932 KB Output is correct
2 Correct 681 ms 58744 KB Output is correct
3 Correct 690 ms 58616 KB Output is correct
4 Correct 720 ms 60280 KB Output is correct
5 Correct 717 ms 60536 KB Output is correct
6 Correct 807 ms 62328 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 2808 KB Output is correct
2 Correct 36 ms 2936 KB Output is correct
3 Correct 33 ms 2936 KB Output is correct
4 Correct 32 ms 2936 KB Output is correct
5 Correct 11 ms 3320 KB Output is correct
6 Correct 11 ms 3320 KB Output is correct
7 Correct 11 ms 3320 KB Output is correct
8 Correct 11 ms 3320 KB Output is correct
9 Correct 11 ms 3320 KB Output is correct
10 Correct 11 ms 3320 KB Output is correct
11 Correct 11 ms 3320 KB Output is correct
12 Correct 11 ms 3320 KB Output is correct
13 Correct 11 ms 3320 KB Output is correct
14 Correct 11 ms 3320 KB Output is correct
15 Correct 645 ms 58932 KB Output is correct
16 Correct 681 ms 58744 KB Output is correct
17 Correct 690 ms 58616 KB Output is correct
18 Correct 720 ms 60280 KB Output is correct
19 Correct 717 ms 60536 KB Output is correct
20 Correct 807 ms 62328 KB Output is correct
21 Correct 620 ms 61612 KB Output is correct
22 Correct 650 ms 61304 KB Output is correct
23 Correct 660 ms 61304 KB Output is correct
24 Correct 701 ms 63224 KB Output is correct
25 Correct 736 ms 66040 KB Output is correct
26 Correct 603 ms 61948 KB Output is correct
27 Correct 639 ms 61432 KB Output is correct
28 Correct 642 ms 61432 KB Output is correct
29 Correct 702 ms 62840 KB Output is correct
30 Correct 757 ms 64248 KB Output is correct
31 Correct 605 ms 62328 KB Output is correct
32 Correct 625 ms 62072 KB Output is correct
33 Correct 661 ms 62072 KB Output is correct
34 Correct 736 ms 63864 KB Output is correct
35 Correct 735 ms 66552 KB Output is correct
36 Correct 662 ms 64120 KB Output is correct