Submission #132606

#	Time	Username	Problem	Language	Result	Execution time	Memory
132606		EntityIT	Valley (BOI19_valley)	C++14	32 / 100	346 ms	54748 KiB

valley

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

using ll = long long;
const int N = (int)1e5 + 5, LOG = __lg(N) + 1, inf = (int)1e9 + 123;
const ll infll = (ll)1e18 + 123;
int n, n_shop, n_query, exit_ver, be[N], en[N], par[N][LOG], depth[N], edge_ver[N];
pair<int, int> edge[N];
ll min_down[N][3], min_up[N], f_minus[N][LOG], f_plus[N][LOG], depth_cap[N];
bool have_shop[N];
vector< pair<int, int> > gr[N];

void dfs (int u, int p) {
    static int i_tour = 0;
    be[u] = ++i_tour;

    par[u][0] = p;
    for (int i = 1; i < LOG; ++i) par[u][i] = par[ par[u][i - 1] ][i - 1];

    depth[u] = depth[p] + 1;

    for (auto _ : gr[u]) {
        int v = _.fi; edge_ver[v] = _.se;
        if (v == p) continue ;
        depth_cap[v] = depth_cap[u] + edge_ver[v];
        dfs(v, u);
    }
    en[u] = i_tour;
}

int check_bit (int _a, int _i) { return (_a >> _i) & 1; }

int find_lca (int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    int diff = depth[v] - depth[u];
    for (int i = LOG - 1; i >= 0; --i) if (check_bit(diff, i) ) v = par[v][i];
    for (int i = LOG - 1; i >= 0; --i) if (par[u][i] != par[v][i]) {
        u = par[u][i]; v = par[v][i];
    }
    return (u == v) ? u : par[u][0];
}

void cal_min_down (int u) {
    min_down[u][0] = min_down[u][1] = min_down[u][2] = infll;
    if (have_shop[u]) min_down[u][0] = 0;
    for (auto _ : gr[u]) {
        int v = _.fi, w = _.se;
        if (v == par[u][0]) continue ;
        cal_min_down(v);
        ll n_val = min_down[v][0] + w;
        for (int i = 0; i < 3; ++i) if (min_down[u][i] > n_val) swap(min_down[u][i], n_val);
    }
}

void cal_min_up (int u) {
    if (have_shop[u]) min_up[u] = 0;
    for (auto _ : gr[u]) {
        int v = _.fi, w = _.se;
        if (v == par[u][0]) continue ;

        min_up[v] = infll;
        min_up[v] = min(min_up[v], min_up[u] + w);
        if (min_down[v][0] + w == min_down[u][0]) min_up[v] = min(min_up[v], min_down[u][1] + w);
        else min_up[v] = min(min_up[v], min_down[u][0] + w);

        cal_min_up(v);
    }
}

void cal_f (int u) {
    for (int i = 1; i < LOG; ++i) {
        f_minus[u][i] = min(f_minus[u][i - 1], f_minus[ par[u][i - 1] ][i - 1]);
        f_plus[u][i] = min(f_plus[u][i - 1], f_plus[ par[u][i - 1] ][i - 1]);
    }

    for (auto _ : gr[u]) {
        int v = _.fi, w = _.se;
        if (v == par[u][0]) continue ;
        if (min_down[v][0] + w == min_down[u][0]) f_minus[v][0] = f_plus[v][0] = min_down[u][1];
        else f_minus[v][0] = f_plus[v][0] = min_down[u][0];
        f_minus[v][0] -= depth_cap[u];
        f_plus[v][0] += depth_cap[u];
        cal_f(v);
    }
}

bool descendant (int u, int p) { return be[p] <= be[u] && en[u] <= en[p]; }

ll get_f_minus (int u, int heigh) {
    ll ret = infll;
    for (int i = LOG - 1; i >= 0; --i) if (check_bit(heigh, i) ) {
        ret = min(ret, f_minus[u][i]);
        u = par[u][i];
    }
    return ret;
}

ll get_f_plus (int u, int heigh) {
    ll ret = infll;
    for (int i = LOG - 1; i >= 0; --i) if (check_bit(heigh, i) ) {
        ret = min(ret, f_plus[u][i]);
        u = par[u][i];
    }
    return ret;
}

int find_ancestor (int u, int heigh) {
    for (int i = LOG - 1; i >= 0; --i) if (check_bit(heigh, i) ) u = par[u][i];
    return u;
}

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

//    freopen("test.INP", "r", stdin);
//    freopen("test.OUT", "w", stdout);

    cin >> n >> n_shop >> n_query >> exit_ver;
    for (int i = 1; i < n; ++i) {
        int u, v, w; cin >> u >> v >> w;
        gr[u].pb( { v, w } );
        gr[v].pb( { u, w } );
        edge[i] = { u, v };
    }
    while (n_shop --) {
        int ver; cin >> ver; have_shop[ver] = 1;
    }

    dfs(1, 1);
    cal_min_down(1);
    min_up[1] = infll; cal_min_up(1);

    for (int i = 0; i < LOG; ++i) f_minus[1][i] = f_plus[1][i] = infll;
    cal_f(1);

    for (int i = 1; i < n; ++i) if (depth[ edge[i].fi ] > depth[ edge[i].se ]) swap(edge[i].fi, edge[i].se);

    while (n_query --) {
        int edge_id, src; cin >> edge_id >> src;
        int cut_ver = edge[edge_id].se;

        if (descendant(src, cut_ver) == descendant(exit_ver, cut_ver) ) cout << "escaped\n";
        else {
            ll ans = infll;

            int lca = find_lca(src, cut_ver);
            if (lca == cut_ver) {
                ans = min(ans, min_down[src][0]);

                ans = min(ans, depth_cap[src] + get_f_minus(src, depth[src] - depth[cut_ver]) );
            }
            else if (lca == src) {
                ans = min(ans, min_up[src]);

                ans = min(ans, get_f_plus(cut_ver, depth[cut_ver] - depth[src]) - depth_cap[src]);
            }
            else {
                ans = min(ans, min_down[src][0]);

                ans = min(ans, depth_cap[src] + get_f_minus(src, depth[src] - depth[lca] - 1) );

                ans = min(ans, depth_cap[src] - 2 * depth_cap[lca] + get_f_plus(cut_ver, depth[cut_ver] - depth[lca] - 1) );

                ans = min(ans, depth_cap[src] - depth_cap[lca] + min_up[lca]);

                int par_src = find_ancestor(src, depth[src] - depth[lca] - 1),
                    par_cut = find_ancestor(cut_ver, depth[cut_ver] - depth[lca] - 1);
                vector<ll> vec;
                vec.pb(min_down[par_src][0] + edge_ver[par_src]);
                vec.pb(min_down[par_cut][0] + edge_ver[par_cut]);
                sort(vec.begin(), vec.end() );

                for (int i = 0; i < 3; ++i) {
                    if (i > 1 || vec[i] != min_down[lca][i]) {
                        ans = min(ans, depth_cap[src] - depth_cap[lca] + min_down[lca][i]);
                        break ;
                    }
                }
            }

            if (ans > 1LL * inf * N) cout << "oo\n";
            else cout << ans << '\n';
        }
    }

    return 0;
}

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