oj.uz

Submission #123015

# Submission time Handle Problem Language Result Execution time Memory
123015 2019-06-30T01:56:08 Z model_code Valley (BOI19_valley) C++17
100 / 100
 551 ms 39788 KB 
#pragma GCC optimize("Ofast")
#include <stack>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <vector>
#include <utility>
#include <iostream>
#include <string>
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define sz(v) ll(v.size())
#define T1 template<typename T> static
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
const ll INF = ll(2e18) + 666;
T1 ostream& operator<<(ostream& stream, const vector<T>& t);
T1 void print(T x, string end = "\n"){
    cout << x << end;
}
//!pragma
const int N = 1e5+5;
vl adj[N],cost[N];
ll depth[N],root_dist[N],shop_dist[N];
const int K = 17;
ll st[K][N];
int par[K][N];
bool is_shop[N];
void dfs(int u, int p = -1){
    shop_dist[u] = is_shop[u] ? 0 : INF;
    for(int i = 0; i < sz(adj[u]); ++i){
        int v = adj[u][i];
        if(v == p) continue;
        par[0][v] = u;
        depth[v] = depth[u]+1;
        root_dist[v] = root_dist[u]+cost[u][i];
        dfs(v,u);
        shop_dist[u] = min(shop_dist[u],shop_dist[v]+cost[u][i]);
    }
}
int n,e;
vl path;
const int W = 300;
int up_by_w[N];
void opti(int u, int p = -1){
    while(st[0][u] != e && shop_dist[st[0][u]] >= shop_dist[u]){
        int w = up_by_w[st[0][u]];
        if(w != e && shop_dist[w] >= shop_dist[u])
            st[0][u] = w;
        else
            st[0][u] = st[0][st[0][u]];
    }
    up_by_w[u] = st[0][u];
    for(int i = 0; i < W; ++i)
        up_by_w[u] = st[0][up_by_w[u]];
    for(int i = 0; i < sz(adj[u]); ++i){
        int v = adj[u][i];
        if(v == p) continue;
        st[0][v] = u;
        opti(v,u);
    }
}
void prep_st(){
    st[0][e] = e;
    opti(e);
    for(int s = 1; s < K; ++s)
        for(int u = 1; u <= n; ++u)
            st[s][u] = st[s-1][st[s-1][u]];
}
vpii edges;
int get_block(int id){
    int u,v;
    tie(u,v) = edges[id-1];
    return depth[u] > depth[v] ? u : v;
}
void prep_lca(){
    for(int s = 1; s < K; ++s)
        for(int u = 1; u <= n; ++u)
            par[s][u] = par[s-1][par[s-1][u]];
}
int get_lca(int u, int v){
    if(depth[u] < depth[v])
        swap(u,v);
    for(int k = K-1; k >= 0; --k)
        if(depth[par[k][u]] >= depth[v])
            u = par[k][u];
    if(u == v)
        return u;
    for(int k = K-1; k >= 0; --k)
        if(par[k][u] != par[k][v]){
            u = par[k][u];
            v = par[k][v];
        }
    return par[0][u];
}
string solve(int u, int block){
    int lca = get_lca(u,block);
    if(lca != block)
        return "escaped";
    int v = u;
    for(int s = K-1; s >= 0; --s)
        if(depth[st[s][v]] >= depth[block])
            v = st[s][v];
    if(shop_dist[v] == INF)
        return "oo";
    return to_string(shop_dist[v]+root_dist[u]);
}
void _(){
    int s,q;
    cin >> n >> s >> q >> e;
    for(int i = 0; i < n-1; ++i){
        int a,b,w;
        cin >> a >> b >> w;
        adj[a].pb(b);
        adj[b].pb(a);
        cost[a].pb(w);
        cost[b].pb(w);
        edges.pb({a,b});
    }
    for(int i = 0; i < s; ++i){
        int u;
        cin >> u;
        is_shop[u] = true;
    }
    depth[e] = 1;
    dfs(e);
    for(int i = 1; i <= n; ++i)
        if(shop_dist[i] != INF)
            shop_dist[i] -= root_dist[i];
    prep_st();
    prep_lca();
    for(int i = 0; i < q; ++i){
        int id,u;
        cin >> id >> u;
        int block = get_block(id);
        print(solve(u,block));
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
        _();
    }

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5368 KB Output is correct
2 Correct 10 ms 5368 KB Output is correct
3 Correct 11 ms 5368 KB Output is correct
4 Correct 10 ms 5368 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5368 KB Output is correct
2 Correct 10 ms 5368 KB Output is correct
3 Correct 11 ms 5368 KB Output is correct
4 Correct 10 ms 5368 KB Output is correct
5 Correct 8 ms 5496 KB Output is correct
6 Correct 8 ms 5624 KB Output is correct
7 Correct 9 ms 5628 KB Output is correct
8 Correct 8 ms 5496 KB Output is correct
9 Correct 9 ms 5624 KB Output is correct
10 Correct 9 ms 5496 KB Output is correct
11 Correct 9 ms 5496 KB Output is correct
12 Correct 9 ms 5628 KB Output is correct
13 Correct 9 ms 5496 KB Output is correct
14 Correct 9 ms 5624 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 37304 KB Output is correct
2 Correct 447 ms 36668 KB Output is correct
3 Correct 483 ms 36552 KB Output is correct
4 Correct 497 ms 37740 KB Output is correct
5 Correct 482 ms 37864 KB Output is correct
6 Correct 464 ms 38784 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5368 KB Output is correct
2 Correct 10 ms 5368 KB Output is correct
3 Correct 11 ms 5368 KB Output is correct
4 Correct 10 ms 5368 KB Output is correct
5 Correct 8 ms 5496 KB Output is correct
6 Correct 8 ms 5624 KB Output is correct
7 Correct 9 ms 5628 KB Output is correct
8 Correct 8 ms 5496 KB Output is correct
9 Correct 9 ms 5624 KB Output is correct
10 Correct 9 ms 5496 KB Output is correct
11 Correct 9 ms 5496 KB Output is correct
12 Correct 9 ms 5628 KB Output is correct
13 Correct 9 ms 5496 KB Output is correct
14 Correct 9 ms 5624 KB Output is correct
15 Correct 391 ms 37304 KB Output is correct
16 Correct 447 ms 36668 KB Output is correct
17 Correct 483 ms 36552 KB Output is correct
18 Correct 497 ms 37740 KB Output is correct
19 Correct 482 ms 37864 KB Output is correct
20 Correct 464 ms 38784 KB Output is correct
21 Correct 385 ms 37228 KB Output is correct
22 Correct 389 ms 36696 KB Output is correct
23 Correct 437 ms 36460 KB Output is correct
24 Correct 473 ms 37904 KB Output is correct
25 Correct 493 ms 39788 KB Output is correct
26 Correct 397 ms 37548 KB Output is correct
27 Correct 445 ms 36632 KB Output is correct
28 Correct 465 ms 36456 KB Output is correct
29 Correct 435 ms 37508 KB Output is correct
30 Correct 482 ms 38448 KB Output is correct
31 Correct 453 ms 37396 KB Output is correct
32 Correct 406 ms 36840 KB Output is correct
33 Correct 444 ms 36596 KB Output is correct
34 Correct 445 ms 37792 KB Output is correct
35 Correct 439 ms 39788 KB Output is correct
36 Correct 551 ms 38892 KB Output is correct