oj.uz

Submission #474307

# Submission time Handle Problem Language Result Execution time Memory
474307 2021-09-17T22:41:17 Z hidden1 Valley (BOI19_valley) C++14
100 / 100
 283 ms 50508 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e16 + 7;
#define debug(...) cout << "Line: " << __LINE__ << endl; \
    printDebug(", "#__VA_ARGS__, __VA_ARGS__)
template <typename T>
void printDebug(const char* name, T&& arg1) { cout << (name + 2) << " = " << arg1 << endl; }
template <typename T, typename... T2>
void printDebug(const char* names, T&& arg1, T2&&... args) {
    const char* end = strchr(names + 1, ',');
    cout.write(names + 2, end - names - 2) << " = " << arg1 << endl;
    printDebug(end, args...);
}

const ll MAX_N = 1e5 + 10, LOG = 20;
ll par[MAX_N][LOG], mn[MAX_N][LOG];
ll dp[MAX_N], help_dp[MAX_N];
ll d[MAX_N], in[MAX_N], out[MAX_N], tme = -1;
vector<pair<ll, ll> > g[MAX_N];
ll n, s, q, e;
bool good[MAX_N];

void dfs(ll x, ll p) {
    dp[x] = help_dp[x] = mod;
    in[x] = out[x] = ++ tme;

    for(auto it : g[x]) {
        if(it.first == p) {continue;}
        d[it.first] = d[x] + it.second;

        dfs(it.first, x);

        chkmin(dp[x], help_dp[it.first] - 2 * d[x]);
        chkmin(help_dp[x], help_dp[it.first]);
        out[x] = out[it.first];
    }

    if(good[x]) {
        dp[x] = -d[x];
        help_dp[x] = d[x];
    }
}

void lca_calc(ll x, ll p) {
    par[x][0] = p;
    mn[x][0] = min(dp[x], dp[p]);
    for(ll i = 1; i < LOG; i ++) {
        par[x][i] = par[par[x][i - 1]][i - 1];
        mn[x][i] = min(mn[par[x][i - 1]][i - 1], mn[x][i - 1]);
    }
    for(auto it : g[x]) {
        if(it.first == p) {continue;}
        lca_calc(it.first, x);
    }
}

ll ans(ll x, ll y) {
    ll ret = dp[x];
    for(ll i = LOG - 1; i >= 0; i --) {
        if(d[par[x][i]] >= d[y]) {
            chkmin(ret, mn[x][i]);
            x = par[x][i];
        }
    }
    return ret;
}

pair<ll, ll> edges[MAX_N];

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> s >> q >> e;
    for(ll i = 0; i < n - 1; i ++) {
        ll a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
        edges[i + 1] = {a, b};
    }
    for(ll i = 0; i < s; i ++) {
        ll a;
        cin >> a;
        good[a] = true;
    }
    dfs(e, 0);
    for(int i = 0; i < LOG; i ++) {
        mn[1][i] = mod;
        mn[0][i] = mod;
    }
    dp[0] = mod;
    lca_calc(e, 0);

    for(ll i = 0; i < q; i ++) {
        ll a, ind;
        cin >> ind >> a;
        ll lower;
        if(d[edges[ind].first] > d[edges[ind].second]) {
            lower = edges[ind].first;
        } else {
            lower = edges[ind].second;
        }
        if(in[lower] <= in[a] && in[a] <= out[lower]) {
            ll best_lca = ans(a, lower);
            if(best_lca >= 2e15) {
                cout << "oo" << endl;
            } else {
                cout << best_lca + d[a] << endl;
            }
        } else {
            cout << "escaped" << endl;
        }
    }
    return 0;
}

/*
5 2 100 1
1 2 1
2 3 2
3 4 3
4 5 2
3 5
1 5
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2764 KB Output is correct
2 Correct 5 ms 2876 KB Output is correct
3 Correct 5 ms 2892 KB Output is correct
4 Correct 5 ms 2820 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2764 KB Output is correct
2 Correct 5 ms 2876 KB Output is correct
3 Correct 5 ms 2892 KB Output is correct
4 Correct 5 ms 2820 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 4 ms 3148 KB Output is correct
7 Correct 4 ms 3148 KB Output is correct
8 Correct 3 ms 3068 KB Output is correct
9 Correct 4 ms 3148 KB Output is correct
10 Correct 3 ms 3148 KB Output is correct
11 Correct 3 ms 3148 KB Output is correct
12 Correct 3 ms 3148 KB Output is correct
13 Correct 3 ms 3200 KB Output is correct
14 Correct 3 ms 3148 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 45268 KB Output is correct
2 Correct 212 ms 45064 KB Output is correct
3 Correct 222 ms 45368 KB Output is correct
4 Correct 249 ms 47208 KB Output is correct
5 Correct 231 ms 47324 KB Output is correct
6 Correct 283 ms 49476 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2764 KB Output is correct
2 Correct 5 ms 2876 KB Output is correct
3 Correct 5 ms 2892 KB Output is correct
4 Correct 5 ms 2820 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 4 ms 3148 KB Output is correct
7 Correct 4 ms 3148 KB Output is correct
8 Correct 3 ms 3068 KB Output is correct
9 Correct 4 ms 3148 KB Output is correct
10 Correct 3 ms 3148 KB Output is correct
11 Correct 3 ms 3148 KB Output is correct
12 Correct 3 ms 3148 KB Output is correct
13 Correct 3 ms 3200 KB Output is correct
14 Correct 3 ms 3148 KB Output is correct
15 Correct 186 ms 45268 KB Output is correct
16 Correct 212 ms 45064 KB Output is correct
17 Correct 222 ms 45368 KB Output is correct
18 Correct 249 ms 47208 KB Output is correct
19 Correct 231 ms 47324 KB Output is correct
20 Correct 283 ms 49476 KB Output is correct
21 Correct 192 ms 45380 KB Output is correct
22 Correct 186 ms 45252 KB Output is correct
23 Correct 202 ms 45392 KB Output is correct
24 Correct 236 ms 47556 KB Output is correct
25 Correct 252 ms 50508 KB Output is correct
26 Correct 170 ms 45436 KB Output is correct
27 Correct 204 ms 45340 KB Output is correct
28 Correct 221 ms 45448 KB Output is correct
29 Correct 260 ms 47028 KB Output is correct
30 Correct 276 ms 48640 KB Output is correct
31 Correct 193 ms 45520 KB Output is correct
32 Correct 191 ms 45404 KB Output is correct
33 Correct 208 ms 45636 KB Output is correct
34 Correct 251 ms 47452 KB Output is correct
35 Correct 269 ms 50392 KB Output is correct
36 Correct 230 ms 47796 KB Output is correct