Submission #1096671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096671		snowmel	Valley (BOI19_valley)	C++17	0 / 100	60 ms	16980 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 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 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);
    Sparse_Table<Monoid_2> LCA_TABLE;
    auto lca = [&](int u, int v) {
        static bool is_built = false;
        if(is_built == false) {
            is_built = true;
            vector<int> dat(N << 1);
            for(int i = 0; i < N; ++i) {
                int x = ELID(i);
                int y = ERID(i);
                dat[x] = LID[i];
                dat[y] = (parent[i] != -1 ? LID[parent[i]] : -1);
            }
        }
        u = ELID(u), v = ELID(v);
        if(u > v) swap(u, v);
        return V[LCA_TABLE.prod(u, v + 1)];
    };
    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);
        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";
        }
    }
}
};
/*
namespace sub4 {
bool check() {
    return true;
}
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 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);
    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);
        bool fl = true;
        [&]() {
            auto pd = get_path_decomposition(H, y, 1);
            for(auto&& [l, r] : pd) {
                if(l > r) swap(l, r);
                if(seg.prod(l, r + 1) != 0) {
                    fl = false;
                    break;
                }
            }
            seg.set(LID[ut], 0);
        } ();
        if(fl) {
            cout << "escaped\n";
        } else {
            ll res = 1e18;
        }
    }
}
};
*/
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() {
    cout << (~3 & 1);
    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:205:20: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
  205 |     for(int i = 0; auto&& [x, y, z] : edges) {
      |                    ^~~~
valley.cpp:216:10: warning: variable 'lca' set but not used [-Wunused-but-set-variable]
  216 |     auto lca = [&](int u, int v) {
      |          ^~~

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