Submission #667163

#	Time	Username	Problem	Language	Result	Execution time	Memory
667163		enpikku	Valley (BOI19_valley)	C++14	0 / 100	134 ms	35456 KiB

valley

#include <bits/stdc++.h>

using namespace std;

const int NQ_MAX = 1e5 + 1, LOGN = 18;
int n, s, q, root;
vector<pair<int,int>> sas[NQ_MAX];
int dl_drogi[NQ_MAX]; // dlugosc drogi nr i
int dolny[NQ_MAX]; // dolny wierzcholek dla kazdej drogi
bool shop[NQ_MAX]; // czy sklep w danym miejscu
pair<int,int> kol_dfs[NQ_MAX]; // kolejnosc w dfsie
vector<long long> magic(NQ_MAX); // minimalna dlugosc drogi do sklepu w poddrzewie

long long droga_root[NQ_MAX]; // dlugosc drogi do roota

long long lca[NQ_MAX][LOGN];
int wierz_lca[NQ_MAX][LOGN]; // wierzcholki polozone wyzej od danego

int _=0;
void dfs(int u = root, int p = -1)
{
    kol_dfs[u].first = _++;
    for(auto v : sas[u]) if(v.first != p){
        droga_root[v.first] = droga_root[u] + dl_drogi[v.second];

        dfs(v.first, u);

        dolny[v.second] = v.first;
        wierz_lca[v.first][0] = u;
    }

    kol_dfs[u].second = _++;
}

bool pod(int v, int x) // v - pod jakim, x - jaki
{
    return (kol_dfs[v].first <= kol_dfs[x].first && kol_dfs[x].first <= kol_dfs[v].second);
}

void cnt_magic(int u = root, int p = -1)
{
    magic[u] = (shop[u] ? droga_root[u] : LLONG_MAX);
    for(auto v : sas[u]) if(v.first != p){
        cnt_magic(v.first, u);
        magic[u] = min(magic[u], magic[v.first]);
    }
}

void build_lift() // binary lifting
{
    for(int i=1; i<=n; ++i){ lca[i][0] = magic[wierz_lca[i][0]] + droga_root[i]; //cout << magic[wierz_lca[i][0]] << ' ';
    }

    for(int i=1; i<LOGN; ++i){
        for(int j=1; j<=n; ++j){
            wierz_lca[j][i] = wierz_lca[wierz_lca[j][i-1]][i-1];
            lca[j][i] = min(lca[j][i-1], lca[wierz_lca[j][i-1]][i-1] + droga_root[j] - droga_root[wierz_lca[j][i]]);
        }
    }
}

long long nin(int v, int x) // v - dolny wierz z usunietej sciezki, x - ten dla ktorego szukamy
{
    long long ans = LLONG_MAX, base = 0;

    int L = 0, P = LOGN-1;
    while(x != v){
        int l = L, p = P;
        while(l < p){
            int mid = (l + p + 1) / 2;
            if(pod(v, wierz_lca[x][mid])) l = mid;
            else p = mid-1;
        }

        ans = min(ans, lca[x][l] + base);
        base += droga_root[x] - droga_root[wierz_lca[x][l]];
        x = wierz_lca[x][l];
        P = l-1;
    }
    return ans;
}

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> s >> q >> root;
    int a, b, w;
    for(int i=1; i<=n-1; ++i){
        cin >> a >> b >> w;
        dl_drogi[i] = w;
        sas[a].push_back({b, i});
        sas[b].push_back({a, i});
    }
    for(int i=0; i<s; ++i){
        cin >> a;
        shop[a] = true;
    }

    droga_root[root] = 0;
    dfs();
    cnt_magic();
    for(int i=1; i<=n; ++i)
        if(magic[i] != LLONG_MAX)
            magic[i] -= 2*droga_root[i];
    build_lift();

    int dro, curr;
    while(q--){
        cin >> dro >> curr;
        if(!pod(dolny[dro], curr)){
            cout << "escaped" << '\n';
        }
        else{
            long long ans = nin(dolny[dro], curr);
            if(ans != LLONG_MAX) cout << ans << '\n';
            else cout << "oo" << '\n';
        }
    }
}

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