Submission #133187

#	Time	Username	Problem	Language	Result	Execution time	Memory
133187		muradeyn	Valley (BOI19_valley)	C++14	100 / 100	571 ms	47384 KiB

valley

/* Murad Eynizade */

#include <bits/stdc++.h>
#define intt long long
#define fyck ios_base::sync_with_stdio(0);cin.tie(0);
#define F first
#define S second
//#define endl '\n'

using namespace std;

const int maxx = 100001 , lg = 17;

int n , m , q , ex , nxt;

int lvl[maxx] , in[maxx] , dp[maxx] , shop[maxx] , cnt[maxx];

intt dist[maxx] , table[maxx][lg] , close[maxx] , par[maxx][lg];

vector< pair<int,intt> >v[maxx] , arr;

void dfs(int s,int p) {
    dp[s] = 1;
    cnt[s] = shop[s];
    par[s][0] = p;
    in[s] = ++nxt;
    lvl[s] = lvl[p] + 1;
    for (auto to : v[s])
        if (to.F != p) dist[to.F] = dist[s] + to.S , dfs(to.F , s) , dp[s] += dp[to.F] , cnt[s] += cnt[to.F];
}

void build(int s,int p) {
    if (shop[s])close[s] = dist[s];
    else close[s] = 1000000000000000LL;
    for (auto to : v[s]) {
        if (to.F == p)continue;
        build(to.F , s);
        close[s] = min(close[s] , close[to.F]);
    }
}

int x , y , w;

int main() {
    fyck
    cin>>n>>m>>q>>ex;
    for (int i = 1;i<n;i++) {
        cin>>x>>y>>w;
        v[x].push_back({y , w});
        v[y].push_back({x , w});
        arr.push_back({x , y});
    }
    for (int i = 1;i<=m;i++)cin>>x , shop[x] = 1;
    dfs(ex , 0);
    build(ex , 0);
    for (int i = 1;i<=n;i++)close[i] -= 2 * dist[i] , table[i][0] = close[i];
    for (int j = 1;j<lg;j++)
        for (int i = 1;i<=n;i++)
            par[i][j] = par[par[i][j - 1]][j - 1];
    for (int j = 1;j<lg;j++)
        for (int i = 1;i<=n;i++)
            table[i][j] = min(table[i][j - 1],table[par[i][j - 1]][j - 1]);
    int i , r;
    while (q--) {
        cin>>i>>r;
        i--;
        x = arr[i].F; y = arr[i].S;
        if (lvl[x] < lvl[y])swap(x , y);
        intt res = (in[r] >= in[x] && in[r] <= in[x] + dp[x] - 1);
        if (!res)cout<<"escaped"<<endl;
        else if (cnt[x] == 0)cout<<"oo"<<endl;
        else {
            intt res = 1000000000000000LL , re = dist[r];
            int diff = lvl[r] - lvl[x];
            for (int i = 0;i<lg;i++) {
                if ((1 << i) & diff) {
                    res = min(res , table[r][i]);
                    r = par[r][i];
                }
            }
            res = min(res , table[r][0]);
            cout<<res + re<<endl;
        }
    }
}

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