Submission #545862

#	Time	Username	Problem	Language	Result	Execution time	Memory
545862		Stickfish	Valley (BOI19_valley)	C++17	100 / 100	394 ms	43416 KiB

valley

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
using ll = long long;

const int MAXN = 1e5 + 123;
const ll INF = 1e18 + 177013;
const ll LESSINF = 1e14 + 177013;
vector<pair<int, ll>> edg[MAXN];
vector<pair<int, int>> qrs[MAXN];
bitset<MAXN> shop;
int tin[MAXN];
int tout[MAXN];
ll depth[MAXN];
vector<int> rtin;
int rt[MAXN];

void dfs(int v) {
    tin[v] = rtin.size();
    rtin.push_back(v);
    for (auto [u, w] : edg[v]) {
        if (u == rt[v])
            continue;
        rt[u] = v;
        depth[u] = depth[v] + w;
        dfs(u);
    }
    tout[v] = rtin.size();
}

struct stree {
    void resize(int n) {
        sz = n;
        t.resize(n * 2 - 1);
        mod.resize(n * 2 - 1);
    }

    void add(int l, int r, ll x) {
        add(0, 0, sz, l, r, x);
    }

    ll get(int l, int r) {
        return get(0, 0, sz, l, r);
    }
 private:
     int sz;
     vector<ll> t;
     vector<ll> mod;

     void add(int ind, int lnd, int rnd, int l, int r, ll x) {
         if (lnd >= l && rnd <= r) {
             t[ind] += x;
             mod[ind] += x;
             return;
         }
         if (lnd >= r || rnd <= l)
             return;
         int mnd = (lnd + rnd) / 2;
         int chd = ind + (mnd - lnd) * 2;
         add(ind + 1, lnd, mnd, l, r, x);
         add(chd, mnd, rnd, l, r, x);
         t[ind] = min(t[ind + 1], t[chd]) + mod[ind];
     }

     ll get(int ind, int lnd, int rnd, int l, int r) {
         if (lnd >= l && rnd <= r) {
             return t[ind];
         }
         if (lnd >= r || rnd <= l)
             return INF;
         int mnd = (lnd + rnd) / 2;
         int chd = ind + (mnd - lnd) * 2;
         return min(get(ind + 1, lnd, mnd, l, r), get(chd, mnd, rnd, l, r)) + mod[ind];
     }
};

bool in_subtree(int u, int paru) {
    return tin[paru] < tin[u] && tin[u] < tout[paru];
}

void ans_qrs(int v, stree& tr, vector<ll>& anss) {
    //cout << v << ": ";
    //for (int i = 0; i < rtin.size(); ++i) {
        //if (shop[rtin[i]])
            //cout << "(" << rtin[i] << ' ' << tr.get(i, i + 1) << ") ";
    //}
    //cout << endl;
    for (auto [u, qi] : qrs[v]) {
        if (u == v) {
            anss[qi] = tr.get(tin[v], tout[v]);
        } else if (in_subtree(u, v)) {
            anss[qi] = min(tr.get(0, tin[u]), tr.get(tout[u], rtin.size()));
        } else if (in_subtree(v, u)) {
            anss[qi] = tr.get(tin[u], tout[u]);
        } else {
            anss[qi] = min(tr.get(0, tin[u]), tr.get(tout[u], rtin.size()));
        }
        //cout << "{" << qi << ' ' << anss[qi] << "} ";
    }
    for (auto [u, w] : edg[v]) {
        if (rt[v] == u)
            continue;
        tr.add(0, rtin.size(), w);
        tr.add(tin[u], tout[u], -w * 2); 
        ans_qrs(u, tr, anss);
        tr.add(0, rtin.size(), -w);
        tr.add(tin[u], tout[u], w * 2); 
    }
}

signed main() {
    int n, s, q, e;
    cin >> n >> s >> q >> e;
    vector<pair<int, int>> roads(n - 1);
    --e;
    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        edg[u].push_back({v, w});
        edg[v].push_back({u, w});
        roads[i] = {u, v};
    }
    for (int i = 0; i < s; ++i) {
        int c;
        cin >> c;
        shop[c - 1] = 1;
    }
    dfs(0);
    for (auto& [ru, rv] : roads) {
        if (rt[rv] == ru)
            swap(rv, ru);
    }
    vector<ll> ans(q);
    for (int qi = 0; qi < q; ++qi) {
        int ri, v;
        cin >> ri >> v;
        --ri, --v;
        int u = roads[ri].first;
        if (e == v) {
            ans[qi] = -1;
        } else if (in_subtree(e, v)) {
            if ((e == u || in_subtree(e, u)) && in_subtree(u, v))
                ans[qi] = -2;
            else
                ans[qi] = -1;
        } else {
            bool sube = in_subtree(e, u) || e == u;
            bool subv = in_subtree(v, u) || v == u;
            if (sube ^ subv)
                ans[qi] = -2;
            else
                ans[qi] = -1;
        }
        //cout << "(" << u << ' ' << v << ' ' << e << ": " << ans[qi] << ") ";
        if (ans[qi] == -2) {
            qrs[v].push_back({roads[ri].first, qi});
        }
    }
    stree tr;
    tr.resize(n);
    for (int i = 0; i < n; ++i) {
        if (shop[rtin[i]])
            tr.add(i, i + 1, depth[rtin[i]]);
        else
            tr.add(i, i + 1, INF);
    }
    ans_qrs(0, tr, ans);
    for (int i = 0; i < q; ++i) {
        if (ans[i] == -1) {
            cout << "escaped\n";
        } else if (ans[i] > LESSINF) {
            cout << "oo\n";
        } else {
            cout << ans[i] << '\n';
        }
    }
}

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