Submission #677868

#	Time	Username	Problem	Language	Result	Execution time	Memory
677868		TS_2392	Valley (BOI19_valley)	C++14	100 / 100	243 ms	62840 KiB

valley

#include <bits/stdc++.h>
#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define dbgp(x) cout << #x << " = (" << (x.fi) << ", " << (x.se) << ") "
#define dbg(x) cout << #x << " = " << (x) << ' '

#define rall(x) (x).rbegin(), (x).rend()
#define all(x) (x).begin(), (x).end()
#define sqr(x) (x) * (x)

#define pct __builtin_popcountll
#define lwb lower_bound
#define upb upper_bound

#define eb emplace_back
#define epl emplace

#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;

typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
typedef pair<ldb, ldb> pld;
typedef pair<double, double> pdd;

template<class T1, class T2> bool minimize(T1 &a, T2 b){
    if(a > b){a = b; return true;} return false;
}
template<class T1, class T2> bool maximize(T1 &a, T2 &b){
    if(a < b){a = b; return true;} return false;
}
const int N = 1e5 + 10;
const ll oo = 1e16;
int n, nDot, qsn, root, Tin[N], Tout[N], Timer, dep[N];
ll jmp[N][18], dpUp[N][18], sumUp[N][18], dp[N];
pii edge[N];
vector<pil> adj[N];
ll lift(int u, int len){
    ll sum = 0, res = oo;
    for(int i = 0; i <= 17; ++i) if(len >> i & 1){
        minimize(res, dpUp[u][i] + sum);
        sum += sumUp[u][i];
        u = jmp[u][i];
    }
    return res;
}
void dfs(int u, int par){
    Tin[u] = ++Timer;
    for(int i = 0; i < adj[u].size(); ++i){
        int v = adj[u][i].fi;
        ll w = adj[u][i].se;
        if(v == par) continue;
        jmp[v][0] = u; sumUp[v][0] = w;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        minimize(dp[u], dp[v] + w);
    }
    for(int i = 0; i < adj[u].size(); ++i){
        int v = adj[u][i].fi;
        ll w = adj[u][i].se;
        if(v == par) continue;
        dpUp[v][0] = min(oo, dp[u] + w);
    }
    Tout[u] = ++Timer;
}
bool IsAncestor(int u, int v){
    return Tin[u] < Tin[v] && Tout[v] < Tout[u];
}
int main(){
    SPEED;
    cin >> n >> nDot >> qsn >> root;
    for(int i = 1; i < n; ++i){
        int u, v, w; cin >> u >> v >> w;
        adj[u].eb(v, w); adj[v].eb(u, w);
        edge[i] = {u, v};
    }
    for(int i = 1; i <= n; ++i) dp[i] = oo;
    for(int i = 1; i <= nDot; ++i){
        int v; cin >> v;
        dp[v] = 0;
    }
    dfs(root, 0);
    for(int i = 1; i <= 17; ++i){
        for(int u = 1; u <= n; ++u) if(jmp[u][i - 1] > 0){
            jmp[u][i] = jmp[jmp[u][i - 1]][i - 1];
            sumUp[u][i] = sumUp[u][i - 1] + sumUp[jmp[u][i - 1]][i - 1];
            dpUp[u][i] = min(dpUp[u][i - 1], sumUp[u][i - 1] + dpUp[jmp[u][i - 1]][i - 1]);
        }
    }
    //dbg(root); cout << '\n';
    while(qsn--){
        int id, u, cur;
        cin >> id >> u;
        if(jmp[edge[id].fi][0] == edge[id].se) cur = edge[id].fi;
        else cur = edge[id].se;
        //dbg(cur); dbg(u);
        if(cur == u || IsAncestor(cur, u)){
            int len = dep[u] - dep[cur];
            ll res = min(dp[u], lift(u, len));
            if(res >= oo) cout << "oo";
            else cout << res;
            cout << '\n';
        }
        else cout << "escaped\n";
    }
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i = 0; i < adj[u].size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~
valley.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i = 0; i < adj[u].size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~

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