oj.uz

Submission #526259

# Submission time Handle Problem Language Result Execution time Memory
526259 2022-02-14T06:05:50 Z Evang Valley (BOI19_valley) C++17
100 / 100
 255 ms 40820 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb(x) push_back(x)
#define eb(args...) emplace_back(args)
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


const int LG = 20;
const int N = 1e5+5;
int n, s, q, e, up[LG][N], dep[N];
ll mag[LG][N], dis[N];
tuple<int, int, int> eg[N];
bool is_shop[N];
vpi adj[N];

int anc(int x, int k){
    for(int i = 0; k > 0; ++i){
        if(k&1)
            x = up[i][x];
        k /= 2;
    }
    return x;
}

int lca(int a, int b){
    a = anc(a, max(0, dep[a]-dep[b]));
    b = anc(b, max(0, dep[b]-dep[a]));
    if(a==b)
        return a;

    for(int i = LG-1; i >= 0; --i)
        if(up[i][a]!=up[i][b]){
            a = up[i][a];
            b = up[i][b];
        }

    return up[0][a];
}

void dfs(int v, int p){
    up[0][v] = p;
    if(is_shop[v])
        mag[0][v] = dis[v];
    else
        mag[0][v] = llinf;

    for(auto[u, w]: adj[v]){
        if(u==p)
            continue;
        dep[u] = dep[v] + 1;
        dis[u] = dis[v] + w;
        dfs(u, v);
        mag[0][v] = min(mag[0][v], mag[0][u]);
    }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#else
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
#endif

    cin >> n >> s >> q >> e;
    for(int i = 1; i < n; ++i){
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].eb(b, w);
        adj[b].eb(a, w);
        eg[i] = {a, b, w};
    }

    while(s--){
        int x;
        cin >> x;
        is_shop[x] = 1;
    }

    dfs(e, 0);
    for(int i = 1; i <= n; ++i)
        if(mag[0][i]<llinf)
            mag[0][i] -= 2*dis[i];

#ifdef _DEBUG
    clog << "Line " << __LINE__ << ":\n";
    for(int i = 1; i <= n; ++i)
        clog << dep[i] << sp << dis[i] << el;
    clog << el;
#endif

    for(int i = 1; i < LG; ++i)
        for(int j = 1; j <= n; ++j){
            up[i][j] = up[i-1][up[i-1][j]];
            mag[i][j] = min(mag[i-1][j], mag[i-1][up[i-1][j]]);
        }

    while(q--){
        int i, r;
        cin >> i >> r;
        auto[v, u, _] = eg[i];
        if(lca(v, r)!=v || lca(u, r) != u){
            cout << "escaped\n";
            continue;
        }
        if(dep[v]<dep[u])
            swap(v, u);
        u = r;

        ll mi = llinf;
        for(int i = LG-1; i >= 0; --i)
            if(dep[up[i][r]] >= dep[v]){
                mi = min(mi, mag[i][r]);
                r = up[i][r];
            }
        mi = min(mi, mag[0][r]);

        if(mi >= llinf)
            cout << "oo\n";
        else
            cout << dis[u] + mi << el;
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3012 KB Output is correct
2 Correct 4 ms 2924 KB Output is correct
3 Correct 4 ms 2948 KB Output is correct
4 Correct 5 ms 3020 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3012 KB Output is correct
2 Correct 4 ms 2924 KB Output is correct
3 Correct 4 ms 2948 KB Output is correct
4 Correct 5 ms 3020 KB Output is correct
5 Correct 2 ms 3120 KB Output is correct
6 Correct 2 ms 3116 KB Output is correct
7 Correct 2 ms 3148 KB Output is correct
8 Correct 2 ms 3148 KB Output is correct
9 Correct 4 ms 3208 KB Output is correct
10 Correct 4 ms 3204 KB Output is correct
11 Correct 2 ms 3148 KB Output is correct
12 Correct 3 ms 3204 KB Output is correct
13 Correct 3 ms 3148 KB Output is correct
14 Correct 2 ms 3148 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 36204 KB Output is correct
2 Correct 149 ms 35892 KB Output is correct
3 Correct 172 ms 35780 KB Output is correct
4 Correct 171 ms 37504 KB Output is correct
5 Correct 172 ms 37716 KB Output is correct
6 Correct 234 ms 39544 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3012 KB Output is correct
2 Correct 4 ms 2924 KB Output is correct
3 Correct 4 ms 2948 KB Output is correct
4 Correct 5 ms 3020 KB Output is correct
5 Correct 2 ms 3120 KB Output is correct
6 Correct 2 ms 3116 KB Output is correct
7 Correct 2 ms 3148 KB Output is correct
8 Correct 2 ms 3148 KB Output is correct
9 Correct 4 ms 3208 KB Output is correct
10 Correct 4 ms 3204 KB Output is correct
11 Correct 2 ms 3148 KB Output is correct
12 Correct 3 ms 3204 KB Output is correct
13 Correct 3 ms 3148 KB Output is correct
14 Correct 2 ms 3148 KB Output is correct
15 Correct 120 ms 36204 KB Output is correct
16 Correct 149 ms 35892 KB Output is correct
17 Correct 172 ms 35780 KB Output is correct
18 Correct 171 ms 37504 KB Output is correct
19 Correct 172 ms 37716 KB Output is correct
20 Correct 234 ms 39544 KB Output is correct
21 Correct 113 ms 36356 KB Output is correct
22 Correct 130 ms 35952 KB Output is correct
23 Correct 195 ms 35932 KB Output is correct
24 Correct 170 ms 38004 KB Output is correct
25 Correct 193 ms 40820 KB Output is correct
26 Correct 157 ms 36436 KB Output is correct
27 Correct 141 ms 36104 KB Output is correct
28 Correct 143 ms 36060 KB Output is correct
29 Correct 168 ms 37488 KB Output is correct
30 Correct 255 ms 39028 KB Output is correct
31 Correct 148 ms 36544 KB Output is correct
32 Correct 134 ms 36408 KB Output is correct
33 Correct 140 ms 36236 KB Output is correct
34 Correct 180 ms 38012 KB Output is correct
35 Correct 190 ms 40684 KB Output is correct
36 Correct 171 ms 38096 KB Output is correct