Submission #1096417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096417		snowmel	Valley (BOI19_valley)	C++17	59 / 100	110 ms	21748 KiB

valley

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, S, Q, H, C;
vector<pair<int,int>> QRS;
vector<tuple<int,int,ll>> edges;
vector<int> villages;
namespace sub12 {
vector<vector<int>> adj;
vector<int> is_village;
bool check() {
    return 1ll * N * Q <= int(1e6);
}
array<ll,3> dfs(int u, int p = -1) {
    array<ll,3> res;
    res[0] = res[1] = 0;
    res[2] = 1e18;
    if(u == H) res[0] = 1;
    if(is_village[u]) {
        res[1] = 1;
        res[2] = 0;
    }
    for(auto&& eid : adj[u]) {
        auto [ut, vt, w] = edges[eid];
        auto v = (ut != u ? ut : vt);
        if(v == p || w == -1) continue;
        auto t = dfs(v, u);
        res[0] |= t[0];
        res[1] |= t[1];
        if(t[1]) res[2] = min(res[2], t[2] + w);
    }
    return res;
}
void solve() {
    adj.assign(N, vector<int>());
    is_village.assign(N, 0);
    for(int i = 0; auto&& [x, y, z] : edges) {
        adj[x].emplace_back(i);
        adj[y].emplace_back(i);
        ++i;
    }
    for(auto&& v : villages) is_village[v] = 1;
    for(auto&& [x, y] : QRS) {
        auto t = get<2>(edges[x]);
        get<2>(edges[x]) = -1;
        auto tt = dfs(y);
        get<2>(edges[x]) = t;
        if(tt[0]) {
            cout << "escaped\n";
        } else if(tt[1]) {
            cout << tt[2] << "\n";
        } else {
            cout << "oo\n";
        }
    }
}
};
template<typename Monoid>
struct SegTree {
    using MX = Monoid;
    using X = typename Monoid::X;
    int n, log, size;
    vector<X> dat;
    SegTree() {}
    template<typename F>
    void build(int _n, F f) {
        n = _n, log = 0;
        while((1 << log) < n) ++log;
        size = 1 << log;
        dat.assign(size << 1, MX::unit());
        for(int i = 0; i < n; ++i) dat[i] = f(i);
        for(int i = size - 1; i >= 1; --i) update(i);
    }
    void set(int k, const X& x) {
        assert(0 <= k && k < n);
        dat[k += size] = x;
        while(k >>= 1) update(k);
    }
    X prod(int l, int r) {
        assert(0 <= l && l <= r && r <= n);
        l += size, r += size;
        X vl = MX::unit(), vr = MX::unit();
        while(l < r) {
            if(l & 1) vl = MX::op(vl, dat[l++]);
            if(r & 1) vr = MX::op(dat[--r], vr);
            l >>= 1, r >>= 1;
        }
        return MX::op(vl, vr);
    }
    void update(int k) { dat[k] = MX::op(dat[k << 1], dat[k << 1 | 1]); }
};
struct Monoid_1 {
    using X = int;
    using value_type = X;
    static constexpr X op(const X& x, const X& y) noexcept { return x | y; }
    static constexpr X unit() noexcept { return 0; }
};
namespace sub3 {
bool check() {
    return S == N;
}
vector<vector<int>> adj;
vector<int> LID, RID, parent, V, head;
void dfs1(int u) {
    auto& sz = RID;
    sz[u] = 1;
    int mx = 0;
    for(auto& eid : adj[u]) {
        auto&& [ut, vt, w] = edges[eid];
        int v = (u != ut ? ut : vt);
        if(v == parent[u]) continue;
        parent[v] = u;
        dfs1(v);
        sz[u] += sz[v];
        if(sz[v] > mx) {
            mx = sz[v];
            swap(eid, adj[u][0]);
        }
    }
}
void dfs2(int u, int& times) {
    LID[u] = times++;
    RID[u] += LID[u];
    V[LID[u]] = u;
    bool heavy = true;
    for(auto&& eid : adj[u]) {
        auto&& [ut, vt, w] = edges[eid];
        int v = (u != ut ? ut : vt);
        if(v == parent[u]) continue;
        head[v] = (heavy ? head[u] : v);
        heavy = false;
        dfs2(v, times);
    }
}
int LCA(int u, int v) {
    for(int i = 25; i--; ) {
        if(LID[u] > LID[v]) swap(u, v);
        if(head[u] == head[v]) return u;
        v = parent[head[v]];
    }
    assert(false);
}
vector<pair<int,int>> get_path_decomposition(int u, int v, bool edge = 0) {
    vector<pair<int,int>> up, down;
    while(true) {
        if(head[u] == head[v]) break;
        if(LID[u] < LID[v]) {
            down.emplace_back(LID[head[v]], LID[v]);
            v = parent[head[v]];
        } else {
            up.emplace_back(LID[u], LID[head[u]]);
            u = parent[head[u]];
        }
    }
    if(LID[u] < LID[v]) down.emplace_back(LID[u] + edge, LID[v]);
    else if(LID[v] + edge <= LID[u]) up.emplace_back(LID[u], LID[v] + edge);
    up.insert(up.end(), down.rbegin(), down.rend());
    return up;
}
void solve() {
    adj.assign(N, vector<int>());
    LID.resize(N);
    RID.resize(N);
    parent.resize(N);
    V.resize(N);
    head.resize(N);
    for(int i = 0; auto&& [x, y, z] : edges) {
        adj[x].emplace_back(i);
        adj[y].emplace_back(i);
        ++i;
    }
    parent[0] = -1;
    dfs1(0);
    int times = 0;
    head[0] = 0;
    dfs2(0, times);
    SegTree<Monoid_1> seg;
    seg.build(N, [](const int& i) { return 0; });
    for(auto&& [x, y] : QRS) {
        auto [ut, vt, w] = edges[x];
        if(LID[ut] < LID[vt]) swap(ut, vt);
        seg.set(LID[ut], 1);
        //cout << LID[ut] << "\n";
        bool fl = true;
        if(LCA(H, y) != ut) {
            auto pd = get_path_decomposition(H, y);
            for(auto&& [l, r] : pd) {
                if(l > r) swap(l, r);
                //cout << l << " " << r << "\n";
                if(seg.prod(l, r + 1) != 0) {
                    fl = false;
                    break;
                }
            }
        }
        seg.set(LID[ut], 0);
        if(fl) {
            cout << "escaped\n";
        } else {
            cout << "0\n";
        }
    }
}
};
void solve() {
    cin >> N >> S >> Q >> H;
    --H;
    edges.resize(N - 1);
    QRS.resize(Q);
    villages.resize(S);
    for(auto& [u, v, w] : edges) {
        cin >> u >> v >> w;
        --u, --v;
    }
    for(auto& v : villages) {
        cin >> v;
        --v;
    }
    for(auto& [x, y] : QRS) {
        cin >> x >> y;
        --x, --y;
    }
    if(sub12::check()) return sub12::solve();
    if(sub3::check()) return sub3::solve();
    sub3::solve();
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while(t--) solve();
}

Compilation message (stderr)

valley.cpp: In function 'void sub12::solve()':
valley.cpp:37:20: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
   37 |     for(int i = 0; auto&& [x, y, z] : edges) {
      |                    ^~~~
valley.cpp: In function 'void sub3::solve()':
valley.cpp:167:20: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
  167 |     for(int i = 0; auto&& [x, y, z] : edges) {
      |                    ^~~~

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