Submission #699916

#	Time	Username	Problem	Language	Result	Execution time	Memory
699916		Shayan86	Valley (BOI19_valley)	C++14	100 / 100	242 ms	66928 KiB

valley

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n';
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

const ll L = 20;
const ll N = 1e5 + 7;
const ll inf = 1e18 + 7;

ll n, S, q, E, h[N], st[N], ft[N], timer, par[N][L], naz[N][L], sub[N][3], dist[N][L];
pll edge[N];

bool mark[N], red[N];
vector<pll> adj[N];

void dfs(int v){
    st[v] = ++timer;
    ll mn = inf, mn2 = inf, idx;

    mark[v] = true;
    for(auto u: adj[v]){
        if(!mark[u.F]){
            h[u.F] = h[v] + 1;
            dfs(u.F);
            if(sub[u.F][0] + u.S < mn){
                mn = sub[u.F][0] + u.S;
                idx = u.F;
            }
            else if(sub[u.F][0] + u.S < mn2){
                mn2 = sub[u.F][0] + u.S;
            }
        }
    }

    if(!red[v]){
        sub[v][0] = mn;
        sub[v][1] = idx;
        sub[v][2] = mn2;
    }
    ft[v] = ++timer;
}

void build(int v, ll w = inf, int parent = 0){
    if(v != sub[parent][1]) naz[v][0] = sub[parent][0] + w;
    else naz[v][0] = sub[parent][2] + w;

    dist[v][0] = w;
    par[v][0] = parent;
    for(int i = 1; i < L; i++){
        //if(!par[v][i-1]) break;
        par[v][i] = par[par[v][i-1]][i-1];
        dist[v][i] = dist[v][i-1] + dist[par[v][i-1]][i-1];
        naz[v][i] = min(naz[v][i-1], naz[par[v][i-1]][i-1] + dist[v][i-1]);
    }

    mark[v] = true;
    for(auto u: adj[v]){
        if(!mark[u.F]){
            build(u.F, u.S, v);
        }
    }
}

int main(){
    fast_io;

    cin >> n >> S >> q >> E;

    int u, v, w;
    for(int i = 1; i < n; i++){
        cin >> u >> v >> w;
        adj[u].pb(Mp(v, w));
        adj[v].pb(Mp(u, w));
        edge[i] = Mp(u, v);
    }

    for(int i = 1; i <= S; i++){
        cin >> v;
        red[v] = true;
    }

    for(int i = 0; i < N; i++){
        fill(naz[i], naz[i] + L, inf);
        fill(dist[i], dist[i] + L, inf);
    }

    sub[0][0] = sub[0][2] = inf;

    dfs(E);
    fill(mark, mark + N, 0); build(E);

    /*for(int i = 1; i <= n; i++){
        for(int j = 0; j < 5; j++){
            cout << i << sep << j << sep << naz[i][j] << sep << dist[i][j] << sep << par[i][j] << endl;
        }
    }*/

    int ii, r;

    while(q--){
        cin >> ii >> r;

        int u = edge[ii].F;
        int v = edge[ii].S;
        if(h[v] < h[u]) swap(u, v);

        if(st[E] <= st[u] && ft[u] <= ft[E] && st[v] <= st[r] && ft[r] <= ft[v]){
            ll res = sub[r][0], fas = 0;

            int c = r;
            for(int i = L-1; i >= 0; i--){
                if(h[par[c][i]] < h[v]) continue;
                res = min(res, naz[c][i] + fas);
                fas += dist[c][i]; c = par[c][i];
            }

            if(res >= inf){
                cout << "oo" << endl; continue;
            }
            cout << res << endl;
        }
        else{
            cout << "escaped" << endl;
        }
    }

}

Compilation message (stderr)

valley.cpp: In function 'void dfs(int)':
valley.cpp:51:19: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |         sub[v][1] = idx;
      |         ~~~~~~~~~~^~~~~

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41