oj.uz

Submission #213553

# Submission time Handle Problem Language Result Execution time Memory
213553 2020-03-26T06:03:01 Z usachevd0 Valley (BOI19_valley) C++14
100 / 100
 248 ms 26232 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()

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

template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }

void debug_out()
{
    cerr << endl;
}

template<typename T1, typename... T2> void debug_out(T1 A, T2... B)
{
    cerr << ' ' << A;
    debug_out(B...);
}

#ifdef DEBUG
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
    #define debug(...) 42
#endif

const int maxN = 100005;
const ll INF64 = 1e18;
int N, S, Q, root;
vector< pair<int, ll> > G[maxN];
bool good[maxN];
int par[maxN];
ll H[maxN];
int tin[maxN], tout[maxN];

ll ans[maxN];
vector<pii> qvtx[maxN];

int timer;
void dfs0(int v, int p = -1)
{
    par[v] = p;
    tin[v] = timer++;
    for (auto e : G[v])
    {
        int u = e.fi;
        ll c = e.se;
        if (u != p)
        {
            H[u] = H[v] + c;
            dfs0(u, v);
        }
    }
    tout[v] = timer - 1;
}

bool upper(int a, int b)
{
    return tin[a] <= tin[b] && tout[b] <= tout[a];
}

namespace sgt
{
    ll t[4 * maxN];

    void init()
    {
        fill(t, t + 4 * maxN, INF64);
    }

    void push(int v, int vl, int vr)
    {
        if (vl != vr)
        {
            chkmin(t[v << 1], t[v]);
            chkmin(t[v << 1 | 1], t[v]);
        }
    }

    void umin(int v, int vl, int vr, int l, int r, ll x)
    {
        if (l > r || vr < l || r < vl) return;
        if (l <= vl && vr <= r)
        {
            chkmin(t[v], x);
            return;
        }
        int vm = (vl + vr) >> 1;
        push(v, vl, vr);
        umin(v << 1, vl, vm, l, r, x);
        umin(v << 1 | 1, vm + 1, vr, l, r, x);
    }

    ll gt(int v, int vl, int vr, int pos)
    {
        if (vl == vr)
        {
            return t[v];
        }
        int vm = (vl + vr) >> 1;
        push(v, vl, vr);
        if (pos <= vm)
            return gt(v << 1, vl, vm, pos);
        else
            return gt(v << 1 | 1, vm + 1, vr, pos);
    }
}

void umin(int l, int r, ll x)
{
    sgt::umin(1, 0, N - 1, l, r, x);
}

ll gt(int pos)
{
    return sgt::gt(1, 0, N - 1, pos);
}

ll dfs1(int v, int p = -1)
{
    ll cd = INF64;
    if (good[v])
    {
        umin(tin[v], tin[v], -H[v]);
        cd = 0;
    }
    for (auto e : G[v])
    {
        int u = e.fi;
        ll c = e.se;
        if (u != p)
        {
            ll cd2 = dfs1(u, v) + c;
            umin(tin[v], tin[u] - 1, -H[v] + cd2);
            umin(tin[u], tout[u], -H[v] + cd);
            chkmin(cd, cd2);
        }
    }
    for (pii q : qvtx[v])
    {
        int u = q.fi;
        int idx = q.se;
        ans[idx] = gt(tin[u]) + H[u];
    }
    return cd;
}

signed main()
{
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> S >> Q >> root;
    pii edges[N - 1];
    for (int i = 0; i < N - 1; ++i)
    {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        G[a].emplace_back(b, c);
        G[b].emplace_back(a, c);
        edges[i] = {a, b};
    }
    while (S--)
    {
        int v;
        cin >> v;
        good[v] = true;
    }
    dfs0(root);
    fill(ans, ans + Q, INF64);
    for (int i = 0; i < Q; ++i)
    {
        int ei, u;
        cin >> ei >> u;
        --ei;
        int v = edges[ei].fi == par[edges[ei].se] ? edges[ei].se : edges[ei].fi;
        if (!upper(v, u))
        {
            ans[i] = -1;
            continue;
        }
        qvtx[v].emplace_back(u, i);
    }
    sgt::init();
    dfs1(root);
    for (int i = 0; i < Q; ++i)
    {
        if (ans[i] == -1)
        {
            cout << "escaped\n";
        }
        else if (ans[i] >= INF64)
        {
            cout << "oo\n";
        }
        else
        {
            cout << (long long)ans[i] << '\n';
        }
    }

    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 18936 KB Output is correct
2 Correct 214 ms 18680 KB Output is correct
3 Correct 229 ms 18680 KB Output is correct
4 Correct 248 ms 20600 KB Output is correct
5 Correct 210 ms 19832 KB Output is correct
6 Correct 236 ms 22392 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8448 KB Output is correct
2 Correct 11 ms 8320 KB Output is correct
3 Correct 11 ms 8448 KB Output is correct
4 Correct 11 ms 8448 KB Output is correct
5 Correct 10 ms 8320 KB Output is correct
6 Correct 10 ms 8320 KB Output is correct
7 Correct 10 ms 8320 KB Output is correct
8 Correct 10 ms 8320 KB Output is correct
9 Correct 10 ms 8320 KB Output is correct
10 Correct 10 ms 8320 KB Output is correct
11 Correct 11 ms 8320 KB Output is correct
12 Correct 12 ms 8320 KB Output is correct
13 Correct 10 ms 8320 KB Output is correct
14 Correct 10 ms 8320 KB Output is correct
15 Correct 225 ms 18936 KB Output is correct
16 Correct 214 ms 18680 KB Output is correct
17 Correct 229 ms 18680 KB Output is correct
18 Correct 248 ms 20600 KB Output is correct
19 Correct 210 ms 19832 KB Output is correct
20 Correct 236 ms 22392 KB Output is correct
21 Correct 185 ms 22136 KB Output is correct
22 Correct 195 ms 22008 KB Output is correct
23 Correct 198 ms 21884 KB Output is correct
24 Correct 215 ms 24056 KB Output is correct
25 Correct 203 ms 26232 KB Output is correct
26 Correct 179 ms 22268 KB Output is correct
27 Correct 191 ms 22008 KB Output is correct
28 Correct 197 ms 22008 KB Output is correct
29 Correct 212 ms 23548 KB Output is correct
30 Correct 205 ms 24568 KB Output is correct
31 Correct 185 ms 22396 KB Output is correct
32 Correct 198 ms 22136 KB Output is correct
33 Correct 200 ms 22136 KB Output is correct
34 Correct 216 ms 24188 KB Output is correct
35 Correct 201 ms 26232 KB Output is correct
36 Correct 196 ms 23416 KB Output is correct