oj.uz

Submission #704168

# Submission time Handle Problem Language Result Execution time Memory
704168 2023-03-01T19:19:36 Z Valera_Grinenko Valley (BOI19_valley) C++17
100 / 100
 214 ms 41116 KB 
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#ifdef __APPLE__

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <immintrin.h>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define D while (false)
#define LOG(...)
#endif

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 42, maxk = 20;

int n, s, q, e;

int timer = 0, tin[maxn], tout[maxn];

int dep[maxn];
ll len[maxn], kek[maxn];

bool shop[maxn];

vector<pair<int, int> > g[maxn];

void dfs(int v, int p) {
    tin[v] = timer++;
    if(shop[v]) kek[v] = len[v];
    else kek[v] = 1e18;
    for(auto& to : g[v])
        if(to.fi != p) {
            dep[to.fi] = dep[v] + 1;
            len[to.fi] = len[v] + to.se;
            dfs(to.fi, v);
            umin(kek[v], kek[to.fi]);
        }
    tout[v] = timer++;
}

int up[maxn][maxk];
ll upkek[maxn][maxk];

ll get(int v, int to) {
    int dist = dep[v] - dep[to];
    ll res = kek[to];
    int cr = v;
    for(int k = 0; k < maxk; k++)
        if(((dist >> k) & 1)) {
            umin(res, upkek[cr][k]);
            cr = up[cr][k];
        }
    return res + len[v];
}

void dfs2(int v, int p) {
    up[v][0] = p;
    upkek[v][0] = kek[v];
    for(int k = 1; k < maxk; k++) {
        up[v][k] = up[up[v][k - 1]][k - 1];
        upkek[v][k] = min(upkek[v][k - 1], upkek[up[v][k - 1]][k - 1]);
    }
    for(auto& to : g[v])
        if(to.fi != p)
            dfs2(to.fi, v);
}

void solve() {
    cin >> n >> s >> q >> e; e--;
    vector<pair<int, int> > edg;
    for(int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[--u].pb({--v, w});
        g[v].pb({u, w});
        edg.pb({v, u});
    }
    for(int i = 0; i < s; i++) {
        int x; cin >> x; shop[--x] = true;
    }
    dfs(e, e);
    for(int i = 0; i < n; i++) kek[i] -= len[i] * 2;
    dfs2(e, e);
    while(q--) {
        int i, v;
        cin >> i >> v;
        i--; v--;
        int to = (dep[edg[i].fi] > dep[edg[i].se] ? edg[i].fi : edg[i].se);
        if(tin[to] <= tin[v] && tout[to] >= tout[v]) {
            ll cur = get(v, to);
            if(cur >= 1e15) cout << "oo\n";
            else cout << cur << '\n';
        } else cout << "escaped\n";
    }
}

signed main() {
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;

    //cin >> t;

    while (t--) solve();

}

/*
KIVI
*/

Subtask #1
9.0 / 9.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2772 KB Output is correct
2 Correct 5 ms 2772 KB Output is correct
3 Correct 4 ms 2772 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 3 ms 3028 KB Output is correct
7 Correct 3 ms 2960 KB Output is correct
8 Correct 2 ms 3028 KB Output is correct
9 Correct 2 ms 3028 KB Output is correct
10 Correct 2 ms 3028 KB Output is correct
11 Correct 3 ms 2956 KB Output is correct
12 Correct 3 ms 3028 KB Output is correct
13 Correct 2 ms 2952 KB Output is correct
14 Correct 3 ms 2956 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 34268 KB Output is correct
2 Correct 153 ms 33904 KB Output is correct
3 Correct 135 ms 33904 KB Output is correct
4 Correct 158 ms 35264 KB Output is correct
5 Correct 154 ms 35492 KB Output is correct
6 Correct 214 ms 36960 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2772 KB Output is correct
2 Correct 5 ms 2772 KB Output is correct
3 Correct 4 ms 2772 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 3 ms 3028 KB Output is correct
7 Correct 3 ms 2960 KB Output is correct
8 Correct 2 ms 3028 KB Output is correct
9 Correct 2 ms 3028 KB Output is correct
10 Correct 2 ms 3028 KB Output is correct
11 Correct 3 ms 2956 KB Output is correct
12 Correct 3 ms 3028 KB Output is correct
13 Correct 2 ms 2952 KB Output is correct
14 Correct 3 ms 2956 KB Output is correct
15 Correct 151 ms 34268 KB Output is correct
16 Correct 153 ms 33904 KB Output is correct
17 Correct 135 ms 33904 KB Output is correct
18 Correct 158 ms 35264 KB Output is correct
19 Correct 154 ms 35492 KB Output is correct
20 Correct 214 ms 36960 KB Output is correct
21 Correct 113 ms 37484 KB Output is correct
22 Correct 139 ms 37172 KB Output is correct
23 Correct 178 ms 37064 KB Output is correct
24 Correct 160 ms 38768 KB Output is correct
25 Correct 176 ms 41116 KB Output is correct
26 Correct 134 ms 37572 KB Output is correct
27 Correct 141 ms 37280 KB Output is correct
28 Correct 132 ms 37180 KB Output is correct
29 Correct 167 ms 38356 KB Output is correct
30 Correct 185 ms 39568 KB Output is correct
31 Correct 112 ms 37664 KB Output is correct
32 Correct 141 ms 37356 KB Output is correct
33 Correct 135 ms 37444 KB Output is correct
34 Correct 165 ms 38760 KB Output is correct
35 Correct 184 ms 40996 KB Output is correct
36 Correct 148 ms 38968 KB Output is correct