oj.uz

답안 #125549

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125549 2019-07-05T21:29:29 Z The_Wolfpack Valley (BOI19_valley) C++14
100 / 100
 505 ms 48376 KB 
#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
#define ll long long
using namespace std;

const int NMAX=1e5+7;
const int LogNMAX=25;
const ll INF=1e18;

int n,s,q,E,tin[NMAX],tout[NMAX],par[LogNMAX][NMAX],lvl[NMAX];
vector<pii> g[NMAX];

ll dp[NMAX], dep[NMAX], mn[LogNMAX][NMAX];

struct edge{int a,b,w;};
edge e[NMAX];
int Time=0;
void Dfs(int son, int p, ll D)
{
    tin[son]=++Time;
    par[0][son]=p;
    dep[son]=D;
    for(pii i:g[son])
    {
        if(i.x==p) continue;
        lvl[i.x]=lvl[son]+1;
        Dfs(i.x, son, D+1LL*i.y);
        dp[son]=min(dp[son],dp[i.x]+1LL*i.y);
    }
    tout[son]=Time;
}

int ok(int A, int B)
{
    return tin[B]<=tin[A] && tout[B]>=tout[A];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin>>n>>s>>q>>E;
    for(int i=0;i<=n;i++) dp[i]=INF;
    for(int i=1;i<=n-1;i++)
    {
        cin>>e[i].a>>e[i].b>>e[i].w;
        g[e[i].a].push_back({e[i].b, e[i].w});
        g[e[i].b].push_back({e[i].a, e[i].w});
    }
    while(s--)
    {
        int c; cin>>c;
        dp[c]=0;
    }
    Dfs(E,0,0);
    for(int i=1;i<=n;i++) if(par[0][e[i].a]==e[i].b) swap(e[i].a, e[i].b);
    for(int i=1;i<=n;i++) mn[0][i]=dp[i]-dep[i];
    for(int i=1;i<LogNMAX;i++) for(int j=1;j<=n;j++)
    {
        par[i][j]=par[i-1][par[i-1][j]];
        mn[i][j]=min(mn[i-1][j], mn[i-1][par[i-1][j]]);
    }
    while(q--)
    {
        int idx,node; cin>>idx>>node;
        idx=e[idx].b;
        if(!ok(node,idx))
        {
            cout<<"escaped"<<endl;
            continue;
        }
        ll res=INF;
        int idi=lvl[node]-lvl[idx]+1;
        int tmp=node;
        for(int i=0;i<LogNMAX;i++)
        {
            if(idi&(1<<i))
            {
                res=min(res,mn[i][node]);
                node=par[i][node];
            }
        }
        res+=dep[tmp];
        if(res>1e17+20) cout<<"oo"<<endl;
        else cout<<res<<endl;
    }
    return 0;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 3192 KB Output is correct
2 Correct 32 ms 3188 KB Output is correct
3 Correct 38 ms 3192 KB Output is correct
4 Correct 32 ms 3064 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 3192 KB Output is correct
2 Correct 32 ms 3188 KB Output is correct
3 Correct 38 ms 3192 KB Output is correct
4 Correct 32 ms 3064 KB Output is correct
5 Correct 8 ms 3320 KB Output is correct
6 Correct 7 ms 3320 KB Output is correct
7 Correct 9 ms 3448 KB Output is correct
8 Correct 8 ms 3452 KB Output is correct
9 Correct 8 ms 3448 KB Output is correct
10 Correct 8 ms 3448 KB Output is correct
11 Correct 8 ms 3448 KB Output is correct
12 Correct 8 ms 3448 KB Output is correct
13 Correct 8 ms 3448 KB Output is correct
14 Correct 8 ms 3320 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 431 ms 44456 KB Output is correct
2 Correct 434 ms 44152 KB Output is correct
3 Correct 460 ms 44116 KB Output is correct
4 Correct 461 ms 45904 KB Output is correct
5 Correct 442 ms 45816 KB Output is correct
6 Correct 484 ms 47992 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 3192 KB Output is correct
2 Correct 32 ms 3188 KB Output is correct
3 Correct 38 ms 3192 KB Output is correct
4 Correct 32 ms 3064 KB Output is correct
5 Correct 8 ms 3320 KB Output is correct
6 Correct 7 ms 3320 KB Output is correct
7 Correct 9 ms 3448 KB Output is correct
8 Correct 8 ms 3452 KB Output is correct
9 Correct 8 ms 3448 KB Output is correct
10 Correct 8 ms 3448 KB Output is correct
11 Correct 8 ms 3448 KB Output is correct
12 Correct 8 ms 3448 KB Output is correct
13 Correct 8 ms 3448 KB Output is correct
14 Correct 8 ms 3320 KB Output is correct
15 Correct 431 ms 44456 KB Output is correct
16 Correct 434 ms 44152 KB Output is correct
17 Correct 460 ms 44116 KB Output is correct
18 Correct 461 ms 45904 KB Output is correct
19 Correct 442 ms 45816 KB Output is correct
20 Correct 484 ms 47992 KB Output is correct
21 Correct 417 ms 44032 KB Output is correct
22 Correct 424 ms 43768 KB Output is correct
23 Correct 427 ms 43384 KB Output is correct
24 Correct 446 ms 45560 KB Output is correct
25 Correct 461 ms 48376 KB Output is correct
26 Correct 409 ms 43968 KB Output is correct
27 Correct 441 ms 43660 KB Output is correct
28 Correct 440 ms 43512 KB Output is correct
29 Correct 454 ms 44984 KB Output is correct
30 Correct 458 ms 46328 KB Output is correct
31 Correct 468 ms 42896 KB Output is correct
32 Correct 456 ms 40284 KB Output is correct
33 Correct 447 ms 40500 KB Output is correct
34 Correct 457 ms 42104 KB Output is correct
35 Correct 505 ms 44844 KB Output is correct
36 Correct 452 ms 42748 KB Output is correct