Submission #1123615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123615		Dreamy_lovesper	Valley (BOI19_valley)	C++20	100 / 100	379 ms	47092 KiB

valley

#include<bits/stdc++.h>

using namespace std;

#define LIFESUCKS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define pb push_back
#define fi first
#define se second
#define debug cout<<"I Love You\n";
#define Bitc(x, j) ((x >> j) & 1)
#define fu(i,a,b) for ( int i = a; i <= b; i++ )
#define fd(i,b,a) for ( int i = b; i >= a; i-- )

const ll Mod = 1e9+7;
const ll inf = 1e15;
const ll lnf = (1ll << 60);

template <class X, class Y>
    bool minimize (X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize (X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }

#define mxn 100007
#define int long long
int numNode, numShop, numQuest, nodeExit;
int shop[mxn];
int h[mxn], g[mxn], uwu[mxn];
ll f[19][mxn], d[19][mxn], node[19][mxn];
ll shortShop[mxn];
vector<pair<int,ll>> graph[mxn];
struct Edge{
    ll u, v, w;
} edge[mxn];

void dfs ( ll u, ll p ) {
    shortShop[u] = (shop[u] ? 0 : lnf);
    for (auto&[v, w] : graph[u]){
        if ( v == p ) continue;
        g[v] = g[u] + w;
        h[v] = h[u] + 1;
        f[0][v] = u;
        dfs(v, u);
        minimize(shortShop[u], shortShop[v] + w);
    }
}

void dfs2 ( ll u ) {
    for ( auto& [v, w] : graph[u]){
        if (v == f[0][u]) continue;
        d[0][v] = shortShop[u] - g[u];
        fu ( i, 1, 17 ) {
            f[i][v] = f[i - 1][f[i - 1][v]];
            d[i][v] = min(d[i - 1][v], d[i - 1][f[i - 1][v]]);
        }
        dfs2(v);
    }
}

ll lca ( ll u, ll v ) {
    if ( h[u] < h[v] ) swap ( u, v );
    ll k = h[u] - h[v];
    fu ( j, 0, 17 ) if ( Bitc(k, j)) u = f[j][u];
    if ( u == v ) return u;
    fd ( j, 17, 0 ) if ( f[j][u] != f[j][v] ) u = f[j][u], v = f[j][v];
    return f[0][u];
}
ll query(ll u, ll v){
    ll dist = h[u] - h[v];
//    cout << u << ' ' << v << ' ' <<dist << '\n';
    ll res = shortShop[u] - g[u];
    fu ( j, 0, 17 ) {
        if (Bitc ( dist, j)) {
            minimize( res, d[j][u] );
            u = f[j][u];
        }
    }
    return res;
}
void lovesper(const ll TestCase){
    cin >> numNode >> numShop >> numQuest >> nodeExit;

    fu ( i, 2, numNode){
        ll u, v, w;cin >> u >> v >> w;
        graph[u].pb({ v, w });
        graph[v].pb({ u, w });
        edge[i - 1] = { u, v, w };
    }

    fu ( i, 1, numShop ) {
        ll x;cin >> x;
        shop[x] = 1;
    }

    memset( d, 0x3f, sizeof(d));
    dfs( nodeExit, 0 );
    dfs2(nodeExit);

    fu ( qst, 1, numQuest ) {
        ll i, s;cin >> i >> s;
        auto [ u, v, w ] = edge[i];
        if ( h[u] < h[v] ) swap(u, v);
        ll p = lca ( s, u );
        if ( u == p ) {
            ll sad = query(s, u) + g[s];
            if ( sad >= lnf ) cout << "oo\n";
            else cout << sad << '\n';
        } else cout << "escaped\n";
    }

}

signed main(){
    LIFESUCKS
    #define name "lovesper"


    ll test=1;
//    cin >> test;
    for (int i = 1; i <= test; i++){
        lovesper(i);
        if ( i < test ) cout << '\n';
    }
    return 0;
}

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