Submission #213537

#	Time	Username	Problem	Language	Result	Execution time	Memory
213537		usachevd0	Valley (BOI19_valley)	C++14	36 / 100	3100 ms	18940 KiB

valley

#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];
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 m, down_m;
    ll s, down_s;
    int sz;
    Node *l, *r;

    Node() {}
    Node(int _v)
    {
        y = rng();
        v = _v;
        sz = 1;
        m = 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->m, x);
        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->m + t->s;
    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->m + t->s << ' ';
        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};
}

ll dist[maxN];
ll dijk(int v, int ban)
{
    fill(dist, dist + N + 1, INF64);
    dist[v] = 0;
    multiset< pair<ll, int> > q;
    q.insert(mp(0, v));
    ll ans = INF64;
    while (!q.empty())
    {
        int v = q.begin()->se;
        ll _d = q.begin()->fi;
        q.erase(q.begin());

        if (_d != dist[v]) continue;
        if (good[v]) chkmin(ans, dist[v]);

        for (auto e : G[v])
        {
            int u = e.fi;
            ll c = e.se;
            if (u != ban)
            {
                if (chkmin(dist[u], dist[v] + c))
                {
                    q.insert(mp(dist[u], u));
                }
            }
        }
    }
    return ans;
}

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))
        {
            cout << "escaped\n";
            continue;
        }
        ll ans = dijk(u, par[v]);
        if (ans == INF64)
            cout << "oo\n";
        else
            cout << ans << '\n';
    }

    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41