Submission #467580

#	Time	Username	Problem	Language	Result	Execution time	Memory
467580		Rico64	Valley (BOI19_valley)	C++14	100 / 100	639 ms	38060 KiB

valley

#include <iostream>
#include <vector>
#include <queue>

const long long INT63_MAX = INT64_MAX / 2;
const int MAX_N = 100000;
const int MAX_LOGN = 17;

struct edge {
    int v, c;
};

using namespace std;

int n, sl, ql, root;
vector<edge> graph[MAX_N];
int ec[MAX_N];
int parent[MAX_N][MAX_LOGN], depth[MAX_N];
long long cost[MAX_N], shopcost[MAX_N];
long long scost[MAX_N][MAX_LOGN];

void search1(int v, int p, long long cc) {
    cost[v] = cc;
    parent[v][0] = p;
    for (int i = 1; i < MAX_LOGN; ++i) {
        parent[v][i] = (p < 0) ? (-1) : (p = parent[p][i-1]);
    }
    for (const edge& e : graph[v]) {
        if (e.v == parent[v][0]) continue;
        depth[e.v] = depth[v] + 1;
        search1(e.v, v, cc + (long long)e.c);
        shopcost[v] = min(shopcost[v], shopcost[e.v] + (long long)e.c);
    }
}

void search2(int v) {
    scost[v][0] = shopcost[v];
    for (int i = 1; i < MAX_LOGN; ++i) {
        int p = parent[v][i-1];
        scost[v][i] = (p < 0) ? (-1) : (min(scost[v][i-1], scost[p][i-1] + cost[v] - cost[p]));
    }
    for (const edge& e : graph[v]) {
        if (e.v == parent[v][0]) continue;
        search2(e.v);
    }
}

int main() {
    cin >> n >> sl >> ql >> root;
    root--;
    int xs[n-1], ys[n-1];
    for (int i = 0, f, t, c; i < n-1; ++i) {
        cin >> f >> t >> c;
        f--; t--;
        xs[i] = f;
        ys[i] = t;
        graph[f].push_back({t, c});
        graph[t].push_back({f, c});
    }
    fill(shopcost, shopcost + n, INT63_MAX);
    for (int i = 0, s; i < sl; ++i) {
        cin >> s;
        s--;
        shopcost[s] = 0;
    }
    depth[root] = 0;
    search1(root, -1, 0);
//    for (int v = 0; v < n; ++v) {
//        for (int i = 0; i < MAX_LOGN; ++i) cout << parent[v][i] << ' ';
//        cout << endl;
//    }
    for (int i = 0; i < n-1; ++i) {
        ec[i] = (parent[xs[i]][0] == ys[i]) ? (xs[i]) : (ys[i]);
    }
//    for (int i = 0; i < n-1; ++i) cout << ec[i] << ' '; cout << endl;
//    for (int i = 0; i < n; ++i) cout << depth[i] << ' '; cout << endl;
//    for (int i = 0; i < n; ++i) cout << cost[i] << ' '; cout << endl;
    search2(root);
//    for (int v = 0; v < n; ++v) {
//        cout << v << " : ";
//        for (int i = 0; i < MAX_LOGN; ++i) cout << scost[v][i] << ' ';
//        cout << endl;
//    }
    ;
    for (int it = 0, i, r; it < ql; ++it) {
        cin >> i >> r;
        i--; r--;
        int c = ec[i];
        int cr = r;
        long long res = INT63_MAX;
        for (int d = depth[r] - depth[c]; d > 0; d ^= d & -d) {
            res = min(res, scost[cr][__builtin_ctz(d)] + cost[r] - cost[cr]);
            cr = parent[cr][__builtin_ctz(d)];
        }
        if (cr != c) {
            cout << "escaped" << endl;
            continue;
        }
        res = min(res, scost[c][0] + cost[r] - cost[c]);
        if (res == INT63_MAX) {
            cout << "oo" << endl;
        } else {
            cout << res << endl;
        }
    }

    return 0;
}

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