oj.uz

답안 #535105

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535105 2022-03-09T12:18:52 Z __Variatto Valley (BOI19_valley) C++17
100 / 100
 430 ms 46172 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=1e5+10, L=19;
const ll MAXV=1e16;
int n, s, q, e, a[MAX], b[MAX], w;
bool sk[MAX];
vector<pair<int,int>>g[MAX];
int czas, pre[MAX], maxiPre[MAX];
ll naj[MAX], gle[MAX], gle2[MAX];
pair<int,ll>jump[MAX][L];
pair<int,int> o[MAX];
void dfs(int v, int oj){
    pre[v]=++czas;
    naj[v]=MAXV;
    if(sk[v])
        naj[v]=0;
    for(auto s:g[v]){
        if(s.fi!=oj){
            gle[s.fi]=gle[v]+1;
            gle2[s.fi]=gle2[v]+s.se;
            o[s.fi]={v, s.se};
            dfs(s.fi, v);
            naj[v]=min(naj[v], naj[s.fi]+(ll)s.se);
        }
    }
    maxiPre[v]=czas;
}
int main(){
/*    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
*/    cin>>n>>s>>q>>e;
    for(int i=1; i<=n-1; i++){
        cin>>a[i]>>b[i]>>w;
        g[a[i]].pb({b[i], w}), g[b[i]].pb({a[i], w});
    }
    for(int i=1; i<=s; i++){
        int c;
        cin>>c;
        sk[c]=true;
    }
    dfs(e, e);
    for(int i=1; i<=n; i++)
        jump[i][0]={o[i].fi, min(naj[i], o[i].se+naj[o[i].fi])};
    for(int i=1; i<L; i++){
        for(int j=1; j<=n; j++){
            jump[j][i].fi=jump[jump[j][i-1].fi][i-1].fi;
            jump[j][i].se=min(jump[j][i-1].se, jump[jump[j][i-1].fi][i-1].se+gle2[j]-gle2[jump[j][i-1].fi]);
        }
    }
    while(q--){
        int x, y;
        cin>>x>>y;
        int u1=a[x], u2=b[x];
        if(pre[u1]>pre[u2])
            swap(u1, u2);
        if(pre[u2]>pre[y] || maxiPre[u2]<pre[y]){
            cout<<"escaped\n";
            continue;
        }
        if(naj[u2]==MAXV){
            cout<<"oo\n";
            continue;
        }
        int doU2=gle[y]-gle[u2];
        //cout<<doU2<<"\n";
        int y1=y, licz=0;
        ll odl=naj[y], akt=0;
        while(doU2){
            if(doU2%2){
                //cout<<y1<<" "<<licz<<" "<<jump[y1][licz].se<<"\n";
                odl=min(odl, akt+jump[y1][licz].se);
                akt+=gle2[y1]-gle2[jump[y1][licz].fi];
                y1=jump[y1][licz].fi;
            }
            doU2/=2, licz++;
        }
        cout<<odl<<"\n";
    }
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 2776 KB Output is correct
2 Correct 23 ms 2764 KB Output is correct
3 Correct 20 ms 2776 KB Output is correct
4 Correct 18 ms 2764 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 2776 KB Output is correct
2 Correct 23 ms 2764 KB Output is correct
3 Correct 20 ms 2776 KB Output is correct
4 Correct 18 ms 2764 KB Output is correct
5 Correct 5 ms 3020 KB Output is correct
6 Correct 4 ms 3012 KB Output is correct
7 Correct 5 ms 3020 KB Output is correct
8 Correct 4 ms 3020 KB Output is correct
9 Correct 5 ms 3020 KB Output is correct
10 Correct 5 ms 3020 KB Output is correct
11 Correct 4 ms 3020 KB Output is correct
12 Correct 5 ms 3020 KB Output is correct
13 Correct 5 ms 3020 KB Output is correct
14 Correct 4 ms 3020 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 375 ms 41664 KB Output is correct
2 Correct 377 ms 41336 KB Output is correct
3 Correct 414 ms 41460 KB Output is correct
4 Correct 419 ms 43056 KB Output is correct
5 Correct 387 ms 43192 KB Output is correct
6 Correct 430 ms 45076 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 2776 KB Output is correct
2 Correct 23 ms 2764 KB Output is correct
3 Correct 20 ms 2776 KB Output is correct
4 Correct 18 ms 2764 KB Output is correct
5 Correct 5 ms 3020 KB Output is correct
6 Correct 4 ms 3012 KB Output is correct
7 Correct 5 ms 3020 KB Output is correct
8 Correct 4 ms 3020 KB Output is correct
9 Correct 5 ms 3020 KB Output is correct
10 Correct 5 ms 3020 KB Output is correct
11 Correct 4 ms 3020 KB Output is correct
12 Correct 5 ms 3020 KB Output is correct
13 Correct 5 ms 3020 KB Output is correct
14 Correct 4 ms 3020 KB Output is correct
15 Correct 375 ms 41664 KB Output is correct
16 Correct 377 ms 41336 KB Output is correct
17 Correct 414 ms 41460 KB Output is correct
18 Correct 419 ms 43056 KB Output is correct
19 Correct 387 ms 43192 KB Output is correct
20 Correct 430 ms 45076 KB Output is correct
21 Correct 343 ms 41816 KB Output is correct
22 Correct 345 ms 41440 KB Output is correct
23 Correct 337 ms 41404 KB Output is correct
24 Correct 415 ms 43228 KB Output is correct
25 Correct 380 ms 46172 KB Output is correct
26 Correct 334 ms 41724 KB Output is correct
27 Correct 379 ms 41344 KB Output is correct
28 Correct 342 ms 41284 KB Output is correct
29 Correct 361 ms 42676 KB Output is correct
30 Correct 390 ms 44136 KB Output is correct
31 Correct 335 ms 41852 KB Output is correct
32 Correct 391 ms 41516 KB Output is correct
33 Correct 345 ms 41628 KB Output is correct
34 Correct 402 ms 43216 KB Output is correct
35 Correct 388 ms 46020 KB Output is correct
36 Correct 352 ms 43928 KB Output is correct