oj.uz

Submission #213543

# Submission time Handle Problem Language Result Execution time Memory
213543 2020-03-26T05:35:58 Z usachevd0 Valley (BOI19_valley) C++14
23 / 100
 241 ms 31224 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

#define int ll

const int maxN = 100005;
const ll INF64 = 4e17;
int N, S, Q, root;
vector< pair<int, ll> > G[maxN];
bool good[maxN];
int par[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;
        if (u != p)
        {
            dfs0(u, v);
        }
    }
    tout[v] = timer - 1;
}

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

mt19937 rng(time(0));
struct Node
{
    int y;
    int v;
    ll f, down_m;
    ll s, down_s;
    int sz;
    Node *l, *r;

    Node() {}
    Node(int _v)
    {
        y = rng();
        v = _v;
        sz = 1;
        f = down_m = INF64;
        s = down_s = 0;
        down_s = 0;
        l = r = 0;
    }
};

int sz(Node *&t)
{
    return t ? t->sz : 0;
}

void upd(Node *&t)
{
    if (t)
    {
        t->sz = sz(t->l) + 1 + sz(t->r);
    }
}

void apply_m(Node *&t, ll x)
{
    if (t)
    {
        chkmin(t->f, x + t->s);
        chkmin(t->down_m, x);
    }
}

void apply_s(Node *&t, ll x)
{
    if (t)
    {
        t->s += x;
        t->down_s += x;
    }
}

void push(Node *&t)
{
    if (!t) return;
    if (t->down_s)
    {
        apply_s(t->l, t->down_s);
        apply_s(t->r, t->down_s);
        t->down_s = 0;
    }
    if (t->down_m < INF64)
    {
        apply_m(t->l, t->down_m);
        apply_m(t->r, t->down_m);
        t->down_m = INF64;
    }
}

Node* merge(Node *a, Node *b)
{
    if (!a) return b;
    if (!b) return a;
    if (a->y > b->y)
    {
        push(a);
        a->r = merge(a->r, b);
        upd(a);
        return a;
    }
    else
    {
        push(b);
        b->l = merge(a, b->l);
        upd(b);
        return b;
    }
}

ll gt(Node *t, int k)
{
    if (!t) return INF64;
    int szl = sz(t->l);
    if (k == szl)
        return t->f;
    push(t);
    if (k < szl)
        return gt(t->l, k);
    else
        return gt(t->r, k - szl - 1);
}

void Tdebug(Node *t)
{
    if (t)
    {
        push(t);
        Tdebug(t->l);
        cout << t->v << '|' << t->f << ' ';
        Tdebug(t->r);
    }
}

pair<Node*, ll> dfs1(int v, int p = -1)
{
    Node* T = new Node(v);
    ll closest_down = INF64;
    if (good[v])
    {
        apply_m(T, 0);
        closest_down = 0;
    }
    for (auto e : G[v])
    {
        int u = e.fi;
        ll c = e.se;
        if (u != p)
        {
            auto res = dfs1(u, v);
            auto Q = res.fi;
            ll cd = res.se + c;
            apply_m(T, cd);
            apply_s(Q, c);
            apply_m(Q, closest_down);
            T = merge(T, Q);
            chkmin(closest_down, cd);
        }
    }
    for (pii q : qvtx[v])
    {
        int u = q.fi;
        int idx = q.se;
        int pos = tin[u] - tin[v];
        ans[idx] = gt(T, pos);
    }
//    debug(v, closest_down); Tdebug(T); cout << endl;
    return {T, closest_down};
}

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;
        ll 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);
    }
    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 << ans[i] << '\n';
        }
    }

    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 5376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 5376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 27948 KB Output is correct
2 Correct 224 ms 27640 KB Output is correct
3 Correct 228 ms 27596 KB Output is correct
4 Correct 241 ms 29436 KB Output is correct
5 Correct 199 ms 28664 KB Output is correct
6 Correct 239 ms 31224 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 5376 KB Output isn't correct
2 Halted 0 ms 0 KB -