oj.uz

Submission #364168

# Submission time Handle Problem Language Result Execution time Memory
364168 2021-02-08T10:32:56 Z jainbot27 Valley (BOI19_valley) C++17
100 / 100
 349 ms 44012 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()
 
#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)
 
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
 
template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const char nl = '\n';
const int mxN = 1e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
 
int n, s, q, e;
vector<pair<int, ll>> adj[mxN];
bool shop[mxN];
int depth[mxN];
ll near[mxN];
ll dist[mxN];
int anc[mxN][20];
ll magic[mxN];
ll best[mxN][20];
pii edges[mxN];
 
void dfs(int u, int p){
    anc[u][0] = p;
    //cout << u << ' '<< dist[u] << nl;
    FOR(i, 1, 20){
        if(anc[u][i-1]==-1) anc[u][i] = -1;
        else anc[u][i] = anc[anc[u][i-1]][i-1];
    }
    near[u] = infLL;
    trav(v, adj[u]){
        if(v.f == p) continue;
        dist[v.f] = dist[u]+v.s;
        depth[v.f] = depth[u]+1;
        dfs(v.f, u);
        ckmin(near[u], near[v.f]+v.s);
    }
    if(shop[u]) near[u] = 0;
    magic[u] = -dist[u]+near[u];
    best[u][0] = magic[u];
}
void dfs2(int u, int p){
    //cout << u << ' ' << magic[u] << nl;
    FOR(i, 1, 20){
        if(anc[u][i-1]==-1) best[u][i]=magic[u];
        else best[u][i] = min(best[anc[u][i-1]][i-1], best[u][i-1]);
    }
    trav(v, adj[u]){
        if(v.f!=p){
            dfs2(v.f, u); 
        }
    }
}
 
int lca(int e1, int e2){
    if(depth[e1] < depth[e2]){
        swap(e1, e2);
    }
    int Dist = depth[e1] - depth[e2];
    R0F(i, 20){
        if((Dist)&(1<<i)){
            e1 = anc[e1][i];
        }
    }
    assert(depth[e1]==depth[e2]);
    if(e1 == e2) return e1;
    R0F(i, 20){
        if(anc[e1][i]!=anc[e2][i]) e1 = anc[e1][i], e2 = anc[e2][i];
    }
    assert(anc[e1][0] == anc[e2][0]);
    return anc[e1][0];
}
 
int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> s >> q >> e; e--;
    F0R(i, n-1){
        int e1, e2, e3;
        cin >> e1 >> e2 >> e3; e1--; e2--;
        edges[i] = {e1, e2};
        adj[e1].pb({e2, e3});
        adj[e2].pb({e1, e3});
    }
    F0R(i, s){
        int e1; cin >> e1;
        shop[e1-1] = 1;
    }
    dfs(e, -1);
    dfs2(e, -1);
    F0R(qq, q){
        int i, r;
        cin >> i >> r;
        i--; r--; 
        if(depth[edges[i].f]<depth[edges[i].s]) swap(edges[i].f, edges[i].s);
        int ans = lca(edges[i].f, r);
        if(ans != edges[i].f) cout << "escaped\n";
        else{
            ll res = infLL;
            int R = r;
            F0R(j, 20){
                if((depth[R]-depth[edges[i].f]+1)&(1<<j)){
                    ckmin(res, dist[R]+best[r][j]);
                    r=anc[r][j];
                }
            }
            if(res>=(ll)1e15) cout << "oo\n";
            else cout << res << nl;
        }
    }
 
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2796 KB Output is correct
2 Correct 5 ms 2924 KB Output is correct
3 Correct 5 ms 2924 KB Output is correct
4 Correct 5 ms 2924 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2796 KB Output is correct
2 Correct 5 ms 2924 KB Output is correct
3 Correct 5 ms 2924 KB Output is correct
4 Correct 5 ms 2924 KB Output is correct
5 Correct 3 ms 3180 KB Output is correct
6 Correct 4 ms 3052 KB Output is correct
7 Correct 3 ms 3180 KB Output is correct
8 Correct 3 ms 3180 KB Output is correct
9 Correct 3 ms 3052 KB Output is correct
10 Correct 3 ms 3180 KB Output is correct
11 Correct 3 ms 3180 KB Output is correct
12 Correct 5 ms 3180 KB Output is correct
13 Correct 3 ms 3308 KB Output is correct
14 Correct 3 ms 3180 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 35564 KB Output is correct
2 Correct 238 ms 35552 KB Output is correct
3 Correct 244 ms 35820 KB Output is correct
4 Correct 285 ms 37484 KB Output is correct
5 Correct 269 ms 37740 KB Output is correct
6 Correct 335 ms 39788 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2796 KB Output is correct
2 Correct 5 ms 2924 KB Output is correct
3 Correct 5 ms 2924 KB Output is correct
4 Correct 5 ms 2924 KB Output is correct
5 Correct 3 ms 3180 KB Output is correct
6 Correct 4 ms 3052 KB Output is correct
7 Correct 3 ms 3180 KB Output is correct
8 Correct 3 ms 3180 KB Output is correct
9 Correct 3 ms 3052 KB Output is correct
10 Correct 3 ms 3180 KB Output is correct
11 Correct 3 ms 3180 KB Output is correct
12 Correct 5 ms 3180 KB Output is correct
13 Correct 3 ms 3308 KB Output is correct
14 Correct 3 ms 3180 KB Output is correct
15 Correct 206 ms 35564 KB Output is correct
16 Correct 238 ms 35552 KB Output is correct
17 Correct 244 ms 35820 KB Output is correct
18 Correct 285 ms 37484 KB Output is correct
19 Correct 269 ms 37740 KB Output is correct
20 Correct 335 ms 39788 KB Output is correct
21 Correct 204 ms 39020 KB Output is correct
22 Correct 235 ms 38764 KB Output is correct
23 Correct 255 ms 38892 KB Output is correct
24 Correct 275 ms 41196 KB Output is correct
25 Correct 349 ms 44012 KB Output is correct
26 Correct 193 ms 39036 KB Output is correct
27 Correct 219 ms 38892 KB Output is correct
28 Correct 251 ms 39020 KB Output is correct
29 Correct 293 ms 40556 KB Output is correct
30 Correct 331 ms 42220 KB Output is correct
31 Correct 201 ms 39020 KB Output is correct
32 Correct 228 ms 38892 KB Output is correct
33 Correct 245 ms 39148 KB Output is correct
34 Correct 297 ms 41196 KB Output is correct
35 Correct 307 ms 44012 KB Output is correct
36 Correct 275 ms 40940 KB Output is correct