제출 #1123467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123467		Dreamy_lovesper	Valley (BOI19_valley)	C++20	0 / 100	3096 ms	55616 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 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
int numNode, numShop, numQuest, nodeExit;
int shop[mxn], subShop[mxn];
int h[mxn], g[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 ) {
    subShop[u] = ( shop[u] );
    for ( auto & [v, w]: graph[u] ) {
        if ( v == p ) continue;
        h[v] = h[u] + 1;
        g[v] = g[u] + w;
        if ( shop[v] ) shortShop[v] = 0;
        else minimize ( shortShop[v], shortShop[u] + w );
        dfs ( v, u );
        subShop[u] += subShop[v];
        if ( shop[u] ) shortShop[u] = 0;
        else 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[v];
        fu ( j, 1, 17 ) {
            f[j][v] = f[j-1][f[j - 1][v]];
            node[j][v] = node[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];
}

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;
        shortShop[x] = 0;
    }

    memset( shortShop, 0x3f, sizeof(shortShop));
    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;
        auto [ u, v, w ] = edge[i];
        ll p = lca ( s, v );
        if ( v == p ) {
            ll sad = shortShop[s];
            ll t, a = s, cr = lnf;
            ll k = h[s] - h[v] - 1;
            fu ( j, 0, 17 ) {
                if ( !Bitc(k, j)) continue;
                if ( minimize(cr, f[j][a] )) t = node[j][a];
                a = f[j][a];
            }
            if ( subShop[v] <= 0 ) cout << "oo" << '\n';
            else {
                p = lca ( t, s );
//                cout << g[p] - g[t] << '\n';
                minimize ( sad, shortShop[t] + ( g[s] - g[t] ));
                cout << sad << '\n';
            }

        } else cout << "escaped\n";
    }

}

signed main(){
    LIFESUCKS
    #define name "lovesper"
    // freopen(name".inp", "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;
}

컴파일 시 표준 에러 (stderr) 메시지

valley.cpp: In function 'long long int lca(long long int, long long int)':
valley.cpp:82:1: warning: control reaches end of non-void function [-Wreturn-type]
   82 | }
      | ^

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