Submission #498013

#	Time	Username	Problem	Language	Result	Execution time	Memory
498013		Nalrimet	Valley (BOI19_valley)	C++17	100 / 100	316 ms	117764 KiB

valley

#include<bits/stdc++.h>

//#pragma GCC optimization("g", on)
//#pragma GCC optimize ("inline")
//#pragma GCC optimization("03")
//#pragma GCC optimization("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popused,abm,mmx,avx,tune=native")
using namespace std;

const int N = 1e6 + 5;
const long long inf = 1e18;
const int K = 25;
#define ll long long
#define int long long

#define F first
#define S second
#define pb push_back

int n, s, q, e, p[N], a[N], b[N], dp[N], dist[N], tin[N], tout[N], timer, mn[N][50], up[N][50];
vector<pair<int, int>> g[N];

void dfs(int v, int pr){
    tin[v] = timer++;
    up[v][0] = pr;
    for(auto to : g[v]){
        if(to.F != pr){
            dist[to.F] = dist[v] + to.S;
            dfs(to.F, v);
            p[v] = min(p[v], p[to.F] + to.S);
        }
    }
    for(auto to : g[v]){
		if(to.F != pr){
			mn[to.F][0] = p[v] - dist[v];
		}
	}
//    dp[v] = p[v] - dist[v];

    tout[v] = timer++;
}

bool is(int a, int b){
    if(tin[a] <= tin[b] && tout[b] <= tout[a]) return 1;
    else return 0;
}

void build(int v, int pr){
    for(int i = 1; i <= K; ++i){
        up[v][i] = up[up[v][i - 1]][i - 1];
        mn[v][i] = min(mn[v][i - 1], mn[up[v][i - 1]][i - 1]);
    }
    for(auto to : g[v])
        if(to.F != pr)
            build(to.F, v);
}

int lift(int u, int v){
    int res = inf, x = v;
    for(int i = K; i >= 0; --i){
//        cout << u << ' ' << up[x][i] << '\n';
        if(is(u, up[x][i])){
//            cout << "Yes\n";
//            cout << mn[x][i] << '\n';
            res = min(res, mn[x][i]);
            x = up[x][i];
        }
    }
    res += dist[v];
    res = min(res, p[v]);

    return res;
}

 main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> s >> q >> e;

    for(int i = 1; i <= n; ++i){
        p[i] = inf;
    }

    for(int i = 1, u, v, w; i < n; ++i){
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
        a[i] = u;
        b[i] = v;
    }

    for(int i = 1, j; i <= s; ++i){
        cin >> j;
        p[j] = 0;
    }

    dfs(e, -1);
    build(e, -1);

    while(q--){
        int i, v, f;
        cin >> i >> v;
        if(up[a[i]][0] == b[i]) f = a[i];
        else f = b[i];
        if(!is(f, v)) cout << "escaped\n";
        else {
            int ans = lift(f, v);
            if(ans >= 1e15) cout << "oo\n";
            else cout << ans << '\n';
        }
    }
}

Compilation message (stderr)

valley.cpp:77:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 |  main() {
      |  ^~~~

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