oj.uz

Submission #677868

# Submission time Handle Problem Language Result Execution time Memory
677868 2023-01-04T13:22:41 Z TS_2392 Valley (BOI19_valley) C++14
100 / 100
 243 ms 62840 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2900 KB Output is correct
2 Correct 4 ms 2832 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 3 ms 2828 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2900 KB Output is correct
2 Correct 4 ms 2832 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 3 ms 2828 KB Output is correct
5 Correct 3 ms 3212 KB Output is correct
6 Correct 3 ms 3156 KB Output is correct
7 Correct 2 ms 3284 KB Output is correct
8 Correct 2 ms 3208 KB Output is correct
9 Correct 2 ms 3156 KB Output is correct
10 Correct 3 ms 3244 KB Output is correct
11 Correct 3 ms 3156 KB Output is correct
12 Correct 2 ms 3260 KB Output is correct
13 Correct 3 ms 3212 KB Output is correct
14 Correct 3 ms 3208 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 57212 KB Output is correct
2 Correct 151 ms 57084 KB Output is correct
3 Correct 174 ms 57364 KB Output is correct
4 Correct 197 ms 59572 KB Output is correct
5 Correct 171 ms 59704 KB Output is correct
6 Correct 243 ms 62268 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2900 KB Output is correct
2 Correct 4 ms 2832 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 3 ms 2828 KB Output is correct
5 Correct 3 ms 3212 KB Output is correct
6 Correct 3 ms 3156 KB Output is correct
7 Correct 2 ms 3284 KB Output is correct
8 Correct 2 ms 3208 KB Output is correct
9 Correct 2 ms 3156 KB Output is correct
10 Correct 3 ms 3244 KB Output is correct
11 Correct 3 ms 3156 KB Output is correct
12 Correct 2 ms 3260 KB Output is correct
13 Correct 3 ms 3212 KB Output is correct
14 Correct 3 ms 3208 KB Output is correct
15 Correct 140 ms 57212 KB Output is correct
16 Correct 151 ms 57084 KB Output is correct
17 Correct 174 ms 57364 KB Output is correct
18 Correct 197 ms 59572 KB Output is correct
19 Correct 171 ms 59704 KB Output is correct
20 Correct 243 ms 62268 KB Output is correct
21 Correct 124 ms 56684 KB Output is correct
22 Correct 145 ms 56576 KB Output is correct
23 Correct 206 ms 56716 KB Output is correct
24 Correct 184 ms 59360 KB Output is correct
25 Correct 198 ms 62840 KB Output is correct
26 Correct 149 ms 56804 KB Output is correct
27 Correct 153 ms 56592 KB Output is correct
28 Correct 153 ms 56832 KB Output is correct
29 Correct 190 ms 58580 KB Output is correct
30 Correct 208 ms 60460 KB Output is correct
31 Correct 131 ms 56804 KB Output is correct
32 Correct 151 ms 56872 KB Output is correct
33 Correct 166 ms 56908 KB Output is correct
34 Correct 194 ms 59236 KB Output is correct
35 Correct 218 ms 62668 KB Output is correct
36 Correct 185 ms 59248 KB Output is correct