Submission #704168

#	Time	Username	Problem	Language	Result	Execution time	Memory
704168		Valera_Grinenko	Valley (BOI19_valley)	C++17	100 / 100	214 ms	41116 KiB

valley

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#ifdef __APPLE__

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <immintrin.h>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define D while (false)
#define LOG(...)
#endif

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 42, maxk = 20;

int n, s, q, e;

int timer = 0, tin[maxn], tout[maxn];

int dep[maxn];
ll len[maxn], kek[maxn];

bool shop[maxn];

vector<pair<int, int> > g[maxn];

void dfs(int v, int p) {
    tin[v] = timer++;
    if(shop[v]) kek[v] = len[v];
    else kek[v] = 1e18;
    for(auto& to : g[v])
        if(to.fi != p) {
            dep[to.fi] = dep[v] + 1;
            len[to.fi] = len[v] + to.se;
            dfs(to.fi, v);
            umin(kek[v], kek[to.fi]);
        }
    tout[v] = timer++;
}

int up[maxn][maxk];
ll upkek[maxn][maxk];

ll get(int v, int to) {
    int dist = dep[v] - dep[to];
    ll res = kek[to];
    int cr = v;
    for(int k = 0; k < maxk; k++)
        if(((dist >> k) & 1)) {
            umin(res, upkek[cr][k]);
            cr = up[cr][k];
        }
    return res + len[v];
}

void dfs2(int v, int p) {
    up[v][0] = p;
    upkek[v][0] = kek[v];
    for(int k = 1; k < maxk; k++) {
        up[v][k] = up[up[v][k - 1]][k - 1];
        upkek[v][k] = min(upkek[v][k - 1], upkek[up[v][k - 1]][k - 1]);
    }
    for(auto& to : g[v])
        if(to.fi != p)
            dfs2(to.fi, v);
}

void solve() {
    cin >> n >> s >> q >> e; e--;
    vector<pair<int, int> > edg;
    for(int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[--u].pb({--v, w});
        g[v].pb({u, w});
        edg.pb({v, u});
    }
    for(int i = 0; i < s; i++) {
        int x; cin >> x; shop[--x] = true;
    }
    dfs(e, e);
    for(int i = 0; i < n; i++) kek[i] -= len[i] * 2;
    dfs2(e, e);
    while(q--) {
        int i, v;
        cin >> i >> v;
        i--; v--;
        int to = (dep[edg[i].fi] > dep[edg[i].se] ? edg[i].fi : edg[i].se);
        if(tin[to] <= tin[v] && tout[to] >= tout[v]) {
            ll cur = get(v, to);
            if(cur >= 1e15) cout << "oo\n";
            else cout << cur << '\n';
        } else cout << "escaped\n";
    }
}

signed main() {
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;

    //cin >> t;

    while (t--) solve();

}

/*
KIVI
*/

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