Submission #1129536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129536		_karan_gandhi	Valley (BOI19_valley)	C++20	100 / 100	321 ms	78124 KiB

valley

#include<bits/stdc++.h>

#define pl(a) " [" << #a << ": " << (a) << "] "
#define pts(a) " [" << #a << ": { first: " << (a.first) << ", second: " << (a.second) << "}] "

#define all(vi) vi.begin(), vi.end()
#define endl "\n"
#define int long long int

using namespace std;

pair<int, int> n4[4] { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
pair<int, int> n8[8] { {1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {-1, -1}, {-1, 1}, {1, -1} };

int h(int x1, int y1, int x2, int y2) { return abs(x2 - x1) + abs(y2 - y1); }

template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }
    
int pow(int x, int y) { 
    if (y == 0) return 1; 
    if (y % 2 == 0) {
        int a = pow(x, y / 2); 
        return a * a;
    } else {
        int a = pow(x, y / 2);
        a = a * a;

        return a * x;
    }
    assert(false);
    return 0;
}

void set_in(string s) {
    if (s.length() > 0) {
        freopen ((s+".in").c_str(), "r", stdin);
        freopen ((s+".out").c_str(), "w", stdout);
    }
}

vector<vector<pair<int, int>>> adj;
vector<pair<pair<int, int>, int>> edges;
int n, s, q, e, r;
vector<bool> shop;
vector<int> dist, dp, p, depth;

void dfs(int u, int par, int d, int dep) {
    dist[u] = d;
    p[u] = par;
    depth[u] = dep;

    for (auto [v, w] : adj[u]) {
        if (v == par) continue;
        dfs(v, u, d + w, dep + 1);
    }

    dp[u] = 1e18;

    if (shop[u]) dp[u] = dist[u];

    for (auto [v, w] : adj[u]) {
        if (v == par) continue;

        dp[u] = min(dp[u], dp[v]);
    }
}

void solve() {
    cin >> n >> s >> q >> e;

    shop.resize(n);
    dist.resize(n);
    dp.resize(n);
    p.resize(n);
    depth.resize(n);
    adj.resize(n);

    for (int i = 0; i < n - 1; i++) {
        int a, b, c; cin >> a >> b >> c;
        a--, b--;
        edges.emplace_back(make_pair(a, b), c);
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }

    for (int i = 0; i < s; i++) {
        int a; cin >> a;
        shop[a - 1] = 1;
    }

    e--;

    dfs(e, e, 0, 0);

    for (int i = 0; i < n; i++) {
        dp[i] -= 2 * dist[i];
    }

    // build the sparse table
    vector<vector<int>> jmp(n, vector<int>(32, -1));
    vector<vector<int>> jmpdp(n, vector<int>(32, 1e18));

    for (int i = 0; i < n; i++) {
        jmp[i][0] = p[i];
        jmpdp[i][0] = min(dp[i], dp[p[i]]);
    }

    for (int i = 1; i < 32; i++) {
        for (int j = 0; j < n; j++) {
            jmp[j][i] = jmp[jmp[j][i - 1]][i - 1];
            jmpdp[j][i] = min({
                jmpdp[j][i - 1],
                jmpdp[jmp[j][i - 1]][i - 1]
            });
        }
    }

    auto best = [&](int u, int k) {
        int res = dp[u];

        int pow = 31;
        while (k > 0) {
            if (k - (1ll << pow) >= 0) {
                k -= (1ll << pow);
                res = min(res, jmpdp[u][pow]);
                u = jmp[u][pow];
            }

            pow--;
        }

        return res;
    };

    auto check = [&](int u, int v) { // u is above v?
        int pow = 31;
        int k = depth[v] - depth[u];

        while (k > 0) {
            if (k - (1ll << pow) >= 0) {
                k -= (1ll << pow);
                v = jmp[v][pow];
            }

            pow--;
        }

        return u == v;
    };

    while (q--) {
        int a, b; cin >> a >> b;
        a--, b--;
        auto ee = edges[a].first;

        if (check(ee.first, b) && check(ee.second, b)) {
            int one = ee.first;
            if (depth[ee.second] > depth[ee.first]) one = ee.second;

            int res = best(b, depth[b] - depth[one]);

            if (res >= 1e16) {
                cout << "oo" << endl;
            } else {
                cout << res + dist[b] << endl;
            }
        } else {
            cout << "escaped" << endl;
        }
    }
}

void precomp() {
    
}

int32_t main() {
#ifndef DEBUG
    set_in("");
#endif
#ifdef DEBUG
    auto clock_start = chrono::high_resolution_clock::now();
    cout << endl;
#endif
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(16) << fixed;

    int T = 1; 
    // cin >> T;
    precomp();
    for (int t = 1; t <= T; t++) {
        // cout << "Case #" << t << ": ";
        solve();
    }

    // Clock
#ifdef DEBUG
    auto clock_end = chrono::high_resolution_clock::now();
    cout << endl;
    chrono::duration<double> elapsed = clock_end - clock_start;
    cout << "Execution time: " << elapsed.count() << "s" << endl;
#endif
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void set_in(std::string)':
valley.cpp:39:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen ((s+".in").c_str(), "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:40:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen ((s+".out").c_str(), "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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