Submission #1096867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096867		snowmel	Valley (BOI19_valley)	C++17	100 / 100	90 ms	33872 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";
        }
    }
}
};
namespace sub3 {
bool check() {
    return S == N;
}
vector<vector<int>> adj;
vector<int> LID, RID, parent, V, head;
vector<ll> depth;
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;
        depth[v] = depth[u] + w;
        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 ELID(int u) { return (LID[u] << 1) - depth[u]; }
int ERID(int u) { return (RID[u] << 1) - depth[u] - 1; }
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);
    depth.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);
    for(auto&& [x, y] : QRS) {
        auto [ut, vt, w] = edges[x];
        if(LID[ut] < LID[vt]) swap(ut, vt);
        bool flag1 = LID[ut] <= LID[H] && LID[H] < RID[ut];
        bool flag2 = LID[ut] <= LID[y] && LID[y] < RID[ut];
        if(flag1 == flag2) {
            cout << "escaped\n";
        } else {
            cout << "0\n";
        }
    }
}
};
template<typename Monoid>
struct Sparse_Table {
    using MX = Monoid;
    using X = typename MX::value_type;
    int n, log;
    vector<vector<X>> dat;
    Sparse_Table() {}
    template<typename F>
    void build(int _n, F f) {
        n = _n, log = 0;
        while((1 << log) <= n) ++log;
        dat.assign(log, vector<X>());
        dat[0].resize(n);
        for(int i = 0; i < n; ++i) dat[0][i] = f(i);
        for(int i = 1; i < log; ++i) {
            dat[i].resize(dat[i - 1].size() - (1 << i - 1));
            for(int j = 0; j < dat[i].size(); ++j) dat[i][j] = MX::op(dat[i - 1][j], dat[i - 1][j + (1 << i - 1)]);
        }
    }
    X prod(int l, int r) {
        assert(0 <= l && l <= r && r <= n);
        if(l == r) return MX::unit();
        if(l + 1 == r) return dat[0][l];
        int k = (31 - __builtin_clz(r - l - 1));
        return MX::op(dat[k][l], dat[k][r - (1 << k)]);
    }
};
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; }
};
struct Monoid_2 {
    using X = ll;
    using value_type = X;
    static constexpr X op(const X& x, const X& y) noexcept { return min(x, y); }
    static constexpr X unit() noexcept { return 1e18; }
};
namespace sub4 {
bool check() {
    return true;
}
vector<vector<int>> adj;
vector<int> LID, RID, parent, V, head;
vector<ll> depth, min_path;
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;
        depth[v] = depth[u] + w;
        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);
    }
}
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 dfs3(int u) {
    for(auto&& eid : adj[u]) {
        auto&& [ut, vt, w] = edges[eid];
        int v = (u != ut ? ut : vt);
        if(v == parent[u]) continue;
        dfs3(v);
        min_path[u] = min(min_path[u], min_path[v] + w);
    }
}
void solve() {
    adj.assign(N, vector<int>());
    LID.resize(N);
    RID.resize(N);
    parent.resize(N);
    V.resize(N);
    head.resize(N);
    depth.resize(N);
    min_path.assign(N, 1e18);
    for(int i = 0; auto&& [x, y, z] : edges) {
        adj[x].emplace_back(i);
        adj[y].emplace_back(i);
        ++i;
    }
    depth[H] = 0;
    parent[H] = -1;
    dfs1(H);
    int times = 0;
    head[H] = H;
    dfs2(H, times);
    for(auto&& u : villages) min_path[u] = 0;
    dfs3(H);
    Sparse_Table<Monoid_2> st;
    st.build(N, [&](const int& i) { return min_path[V[i]] - depth[V[i]]; });
    //for(int i = 0; i < N; ++i) cout << V[i] << " "; cout << "\n";
    //for(int i = 0; i < N; ++i) cout << tb1.prod(i, i + 1) << " "; cout << "\n";
    //for(int i = 0; i < N; ++i) cout << tb2.prod(i, i + 1) << " "; cout << "\n";
    for(auto&& [x, y] : QRS) {
        auto [ut, vt, w] = edges[x];
        if(LID[ut] < LID[vt]) swap(ut, vt);
        bool flag = !(LID[ut] <= LID[y] && LID[y] < RID[ut]);
        if(flag) {
            cout << "escaped\n";
        } else {
            ll res = 1e17;
            auto pd = get_path_decomposition(y, ut, 0);
            for(auto&& [l, r] : pd) {
                if(l > r) swap(l, r);
                res = min(res, st.prod(l, r + 1) + depth[y]);
            }
            if(res == (ll)(1e17)) cout << "oo\n";
            else cout << res << "\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;
    }
    sub4::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:132:20: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
  132 |     for(int i = 0; auto&& [x, y, z] : edges) {
      |                    ^~~~
valley.cpp: In function 'void sub4::solve()':
valley.cpp:302:20: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
  302 |     for(int i = 0; auto&& [x, y, z] : edges) {
      |                    ^~~~
valley.cpp: In instantiation of 'void Sparse_Table<Monoid>::build(int, F) [with F = sub4::solve()::<lambda(const int&)>; Monoid = Monoid_2]':
valley.cpp:316:75:   required from here
valley.cpp:170:55: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  170 |             dat[i].resize(dat[i - 1].size() - (1 << i - 1));
      |                                                     ~~^~~
valley.cpp:171:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |             for(int j = 0; j < dat[i].size(); ++j) dat[i][j] = MX::op(dat[i - 1][j], dat[i - 1][j + (1 << i - 1)]);
      |                            ~~^~~~~~~~~~~~~~~
valley.cpp:171:109: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  171 |             for(int j = 0; j < dat[i].size(); ++j) dat[i][j] = MX::op(dat[i - 1][j], dat[i - 1][j + (1 << i - 1)]);
      |                                                                                                           ~~^~~

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