Submission #717518

#	Time	Username	Problem	Language	Result	Execution time	Memory
717518		boyliguanhan	Valley (BOI19_valley)	C++17	100 / 100	175 ms	39628 KiB

valley

#include <bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define ll __uint128_t
#define V(x) vector<x>
#define G(x) greater<x>
#define MS(x) multiset<x>
#define BG(x) begin(x)
#define All(x) BG(x), end(x)
#define Q(x) queue<x>
#define PQ(x) priority_queue<x, V(x), G(x)>
#define PQG(x) priority_queue<x, V(x), less<x>>
#define OST(x, y) tree<x, null_type, y, rb_tree_tag,tree_order_statistics_node_update>
#define Lb lower_bound
#define Ub upper_bound
#define F first
#define S second
#define T0 get<0>
#define T1 get<1>
#define T2 get<2>
#define P(x) pair<x,x>
#define IO cin.sync_with_stdio(false); cin.tie(nullptr);
#define For(i,a,b,c) for(int i = a; i != b; i+=c)
#define lsb(x) (x&(-x))
#define PB push_back
#define Rm1(a,b) (a.erase(a.find(b)))
#define ER erase
#define Add insert
#define AE(a,b,c) a[b].PB(c)
#define AWE(a,b,c,d) a[b].PB({c,d})
#define AUE(a,b,c) AE(a,b,c), AE(a,c,b)
#define AUWE(a,b,c,d) AWE(a,b,c,d), AWE(a,c,b,d)
#define MOD 1000000007LL
#define HMOD 9999999992999999999ULL
#define FIO(a) freopen((string(a) + ".in").c_str(), "r", stdin), freopen((string(a)+".out").c_str(), "w", stdout)
#define N 100100
V(P(int)) adj[N];
P(int) roads[N];
int hc[N], sz[N], dep[N], val[N], top[N], pos[N], arr[N][20], proc, p[N];
bool shop[N];
void dfs(int n) {
    sz[n] = 1;
    if(!shop[n])
        val[n] = 1e18;
    for(auto i: adj[n]) {
        if(i.F!=p[n]) {
            p[i.F] = n;
            dep[i.F] = dep[n]+i.S;
            dfs(i.F);
            if(sz[hc[n]] < sz[i.F])
                hc[n] = i.F;
            sz[n]+=sz[i.F];
            val[n] = min(val[n], val[i.F]+i.S);
        }
    }
}
void dfs2(int n) {
    if(n!=hc[p[n]])
        top[n] = n;
    else
        top[n] = top[p[n]];
    pos[n] = ++proc;
    val[n]-=dep[n];
    arr[pos[n]][0] = val[n];
    if(hc[n])
        dfs2(hc[n]);
    for(auto i: adj[n]) {
        if(i.F!=p[n]&&i.F!=hc[n]) {
            dfs2(i.F);
        }
    }
}
int query(int l, int r){
    if(l > r)
        swap(l, r);
    int x = 31-__builtin_clz(r-l+1);
    return min(arr[l][x], arr[r-(1<<x)+1][x]);
}
signed main() {
    IO;
    int n, s, q, e;
    cin >> n >> s >> q >> e;
    For(i, 1, n, 1){
        int a, b,c;
        cin >> a >> b >> c;
        AUWE(adj,a,b,c);
        roads[i] = {a, b};
    }
    For(i,1,s+1,1){
        int x;
        cin >> x;
        shop[x]=1;
    }
    dep[e] = 1;
    dfs(e);
    dfs2(e);
    for(int j = 1; j < 20; j++)
        for(int i = 1; i < n - (1 << j) + 2; i++)
            arr[i][j] = min(arr[i][j-1], arr[i+(1<<(j-1))][j-1]);
    for(int i = 0; i < q; i++){
        int x, y;
        cin >> y >> x;
        if(dep[roads[y].F] > dep[roads[y].S])
            y = roads[y].F;
        else
            y = roads[y].S;
        int temp = x;
        while(dep[p[top[temp]]] >= dep[y]) {
            temp = p[top[temp]];
        }
        if(top[temp]!=top[y]||dep[x] < dep[y]) {
            cout << "escaped\n";
        } else {
            int ans = 1e18, add = dep[x];
            while(x!=temp) {
                ans = min(ans, query(pos[top[x]], pos[x]));
                x = p[top[x]];
            }
            ans = min(ans, query(pos[x], pos[y]));
            if(ans > 1e15) {
                cout << "oo\n";
            } else {
                cout << ans + add << '\n';
            }
        }
    }
}

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