Submission #213553

#	Time	Username	Problem	Language	Result	Execution time	Memory
213553		usachevd0	Valley (BOI19_valley)	C++14	100 / 100	248 ms	26232 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];
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 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41