oj.uz

답안 #1096426

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1096426 2024-10-04T12:29:45 Z snowmel Valley (BOI19_valley) C++17
36 / 100
 89 ms 16372 KB 
#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;
        auto pd = get_path_decomposition(H, y, 0);
        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

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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 668 KB Output is correct
2 Correct 8 ms 604 KB Output is correct
3 Correct 9 ms 640 KB Output is correct
4 Correct 9 ms 604 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 668 KB Output is correct
2 Correct 8 ms 604 KB Output is correct
3 Correct 9 ms 640 KB Output is correct
4 Correct 9 ms 604 KB Output is correct
5 Correct 6 ms 348 KB Output is correct
6 Correct 7 ms 572 KB Output is correct
7 Correct 14 ms 604 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 7 ms 344 KB Output is correct
10 Correct 14 ms 600 KB Output is correct
11 Correct 6 ms 348 KB Output is correct
12 Correct 7 ms 580 KB Output is correct
13 Correct 14 ms 604 KB Output is correct
14 Correct 12 ms 588 KB Output is correct

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 89 ms 16372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 668 KB Output is correct
2 Correct 8 ms 604 KB Output is correct
3 Correct 9 ms 640 KB Output is correct
4 Correct 9 ms 604 KB Output is correct
5 Correct 6 ms 348 KB Output is correct
6 Correct 7 ms 572 KB Output is correct
7 Correct 14 ms 604 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 7 ms 344 KB Output is correct
10 Correct 14 ms 600 KB Output is correct
11 Correct 6 ms 348 KB Output is correct
12 Correct 7 ms 580 KB Output is correct
13 Correct 14 ms 604 KB Output is correct
14 Correct 12 ms 588 KB Output is correct
15 Incorrect 89 ms 16372 KB Output isn't correct
16 Halted 0 ms 0 KB -