Submission #1100523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100523		serpent_121	Valley (BOI19_valley)	C++17	23 / 100	337 ms	44476 KiB

valley

#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <numeric>
#include <cmath>
#include <cstring>
#include <climits>
#include <stack>
#include <math.h>
#include <iomanip>
#include <bitset>
typedef long long ll;

using namespace std;
using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pi>;

#define fst first
#define snd second
#define pb push_back
#define rsz resize
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; 
}

template<class T> bool ckmin(T& a, const T& b) { 
	return a > b ? a = b, 1 : 0; 
}

const int MAXN = 1e5;
const ll INF = 1e18;
vector<pair<int, ll>> adj[MAXN];
int st[MAXN], en[MAXN];
ll ht[MAXN]; int par[MAXN];
ll dp[MAXN];
bool shop[MAXN];
int timer = 0;
int e;

void tour(int x, int p) {
    st[x] = timer++;
    dp[x] = INF;
    for (auto cv : adj[x]) {
        int v = cv.fst; ll w = cv.snd;
        if (v!=p) {
            ht[v] = ht[x] + w;
            par[v] = x;
            tour(v, x);
            ckmin(dp[x], dp[v] + w);
        }
    }
    if (shop[x]) dp[x] = 0;
    en[x] = timer;
}

bool is_descendant(int b, int a) {
    return (st[a]<=st[b] && en[a]>=en[b]);
}

pair<int , ll> pow2j[MAXN][18];

void fill(int log2d, int n) {
    par[e] = -1;
    F0R(i, n) pow2j[i][0] = {par[i], (i==e? dp[i] : min(dp[i], dp[par[i]]))};
    for (int p = 1; p< log2d; p++) {
        F0R(i, n) {
            int hway = pow2j[i][p-1].fst;
            if (hway==-1) pow2j[i][p] = {-1, pow2j[i][p-1].snd};
            else pow2j[i][p] = {pow2j[hway][p-1].fst, min(pow2j[i][p-1].snd, pow2j[hway][p-1].snd)};
        }
    }
}

int main() {
    int n, s, q; cin >> n >> s >> q >> e;
    e--;
    vector<pi> roads;
    F0R(i, n-1) {
        int a, b; ll w; cin >> a >> b >> w;
        a--, b--;
        roads.pb({a,b});
        adj[a].pb({b, w}); adj[b].pb({a, w});
    }
    F0R(i, s) {
        int x; cin >> x; x--;
        shop[x] = true;
    }
    tour(e, e);
    int log2d = (int)(log2(n)) + 1;
    fill(log2d, n);
    F0R(i, n) dp[i]-=ht[i];
    // F0R(i, n) cout << ht[i] << endl;
    // cout << "dp: " << endl;
    // F0R(i, n) cout << dp[i] << endl;
    // // F0R(p, log2d) {
    // //     F0R(i, n) {
    // //         cout << pow2j[i][p].fst << " ";
    // //     }
    // //     cout << endl;
    // // }
    // return 0;

    //cout << dp[7] << endl; return 0;
    F0R(j, q) {
        int i, r; cin >> i >> r; r--, i--;
        int top;
        if (is_descendant(roads[i].fst, roads[i].snd)) {
            top = roads[i].fst;
        } else top = roads[i].snd;
        //cout << "top: " << top << endl;
        if (!is_descendant(r, top)) cout << "escaped" << '\n';
        else {
            if (r==top) {
                ll ans = dp[top] + ht[r];
                if (ans>1e14) cout << "oo" << '\n';
                else cout << ans << '\n';
                continue;
            }
            int at = r;
            ll curmin = dp[r];
            for (int p = log2d - 1; p>=0; p--) {
                if (pow2j[at][p].fst!=-1 && !is_descendant(top, pow2j[at][p].fst)) {
                    ckmin(curmin, pow2j[at][p].snd);
                    at = pow2j[at][p].fst;
                    //cout << "from: " << r << " to " <<  at << endl;
                }
            }
            ckmin(curmin, dp[par[at]]);
            //cout << "fin: " << curmin << " " << ht[r] << endl;
            curmin+= ht[r];
            if (curmin>1e14) cout << "oo" << '\n';
            else cout << curmin << '\n';
        }
    }
}

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