제출 #1123616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123616		Dreamy_lovesper	Valley (BOI19_valley)	C++20	23 / 100	327 ms	60416 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 ) {
    for ( auto & [v, w]: graph[u] ) {
        if ( v == p ) continue;
        h[v] = h[u] + 1;
        g[v] = g[u] + w;
        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;
        f[0][v] = u;
        node[0][v] = u;
        d[0][v] = shortShop[u];
        if ( minimize( d[0][v], shortShop[v] ) ) node[0][v] = v;
        fu ( j, 1, 17 ) {
            f[j][v] = f[j-1][f[j - 1][v]];
            node[j][v] = node[j - 1][v];
            d[j][v] = d[j - 1][v];
            if ( d[j][v] > d[j - 1][f[j - 1][v]] ) {
                d[j][v] = d[j - 1][f[j - 1][v]];
                node[j][v] = node[j - 1][f[j - 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];
}

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 };
    }

    memset( shortShop, 0x3f, sizeof(shortShop));
    fu ( i, 1, numShop ) {
        ll x;cin >> x;
        shop[x] = 1;
        shortShop[x] = 0;
    }

    memset( d, 0x3f, sizeof(d));
    dfs( nodeExit, 0 );
    dfs2(nodeExit);
//    fu ( i, 1, numNode ) cout << i << ' ' << shortShop[i] << '\n';

    fu ( i, 2, numNode ){
        auto&[ u, v, w ] = edge[i - 1];
        if ( h[u] > h[v] ) swap ( u, v );
    }

    fu ( qst, 1, numQuest ) {
        ll i, s;cin >> i >> s;
//        cout << '\n';
//        fu ( x, 1, numNode - 1 ) {
//            auto [ aa, bb , cc ] = edge[x];
//            cout << aa << ' ' << bb << ' ' << cc << '\n';
//        }
        auto [ u, v, w ] = edge[i];

        ll p = lca ( s, v );
        if ( v == p ) {
            ll sad = shortShop[s];
            ll t, a = s, cr = lnf;
            if ( shortShop[v] >= 4557430888798830399  ) {
                    cout << "oo" << '\n';
                    continue;
            }
            if ( s == v ) {
                cout << shortShop[v] <<'\n';
                continue;
            }

            if ( v == f[0][s] ){
                if ( shop[v] ) minimize(sad, g[s] - g[v] );
                else minimize(sad, shortShop[v] + (g[s] - g[v]));
                cout << sad << '\n';
                continue;
            }

            ll k = h[s] - h[v] - ( shop[v] ) ;
//            cout << s << ' ' << v << '\n';
//            cout << k << '\n' << '\n';
            fu ( j, 0, 17 ) {
                if ( !Bitc(k, j)) continue;
                if ( minimize(cr, d[j][a] )) t = node[j][a];
//                cout << a << ' ' << d[j][a] << '\n';
                a = f[j][a];
            }

            minimize ( sad, shortShop[t] + abs( g[s] - g[t] ));
            if ( shop[v] ) minimize ( sad, abs(g[s] - g[v]) );
            if ( shop[f[0][s]] ) minimize ( sad, abs( g[s] - g[f[0][s]] ) );
//            cout << t << '\n';
////            cout << cr << '\n';
//            cout << shortShop[t] << ' ' << g[s] - g[t] <<  '\n';
            cout << sad << '\n';
//            cout << '\n';
        } else cout << "escaped\n";
    }

}

signed main(){
    LIFESUCKS
    #define name "lovesper"
    // freopen(name".test", "r", stdin);
    // freopen(name".out", "w", stdout);

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

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