oj.uz

답안 #671197

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
671197 2022-12-12T11:45:08 Z Forested Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 705 ms 58324 KB 
#ifndef LOCAL
#define FAST_IO
#endif

// ============
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define OVERRIDE(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32) (n); ++i)
#define REP3(i, m, n) for (i32 i = (i32) (m); i < (i32) (n); ++i)
#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(i, n) for (i32 i = (i32) (n) - 1; i >= 0; --i)
#define ALL(x) begin(x), end(x)

using namespace std;

using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = __uint128_t;
using i32 = signed int;
using i64 = signed long long;
using i128 = __int128_t;
using f64 = double;
using f80 = long double;

template <typename T>
using Vec = vector<T>;

template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

istream &operator>>(istream &is, i128 &x) {
    i64 v;
    is >> v;
    x = v;
    return is;
}
ostream &operator<<(ostream &os, i128 x) {
    os << (i64) x;
    return os;
}
istream &operator>>(istream &is, u128 &x) {
    u64 v;
    is >> v;
    x = v;
    return is;
}
ostream &operator<<(ostream &os, u128 x) {
    os << (u64) x;
    return os;
}

[[maybe_unused]] constexpr i32 INF = 1000000100;
[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;
struct SetUpIO {
    SetUpIO() {
#ifdef FAST_IO
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
#endif
        cout << fixed << setprecision(15);
    }
} set_up_io;
// ============

#ifdef DEBUGF
#else
#define DBG(x) (void) 0
#endif

// ============

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

class HeavyLightDecomposition {
    std::vector<int> siz;
    std::vector<int> par;
    std::vector<int> hea;
    std::vector<int> in;
    std::vector<int> out;
    std::vector<int> dep;
    std::vector<int> rev;

    template <typename G>
    void dfs1(G &g, int v) {
        if (!g[v].empty() && (int) g[v][0] == par[v]) {
            std::swap(g[v][0], g[v].back());
        }
        for (auto &e : g[v]) {
            int u = (int)e;
            if (u != par[v]) {
                par[u] = v;
                dfs1(g, u);
                siz[v] += siz[u];
                if (siz[u] > siz[(int) g[v][0]]) {
                    std::swap(g[v][0], e);
                }
            }
        }
    }

    template <typename G>
    void dfs2(const G &g, int v, int &time) {
        in[v] = time;
        rev[time++] = v;
        for (auto &e : g[v]) {
            int u = (int)e;
            if (u == par[v]) {
                continue;
            }
            if (u == (int) g[v][0]) {
                hea[u] = hea[v];
            } else {
                hea[u] = u;
            }
            dep[u] = dep[v] + 1;
            dfs2(g, u, time);
        }
        out[v] = time;
    }

public:
    template <typename G>
    HeavyLightDecomposition(G &g, int root = 0) :
        siz(g.size(), 1),
        par(g.size(), root),
        hea(g.size(), root),
        in(g.size(), 0),
        out(g.size(), 0),
        dep(g.size(), 0),
        rev(g.size(), 0) {
        assert(root >= 0 && root < (int) g.size());
        dfs1(g, root);
        int time = 0;
        dfs2(g, root, time);
    }

    int subtree_size(int v) const {
        assert(v >= 0 && v < (int) siz.size());
        return siz[v];
    }

    int parent(int v) const {
        assert(v >= 0 && v < (int) par.size());
        return par[v];
    }

    int in_time(int v) const {
        assert(v >= 0 && v < (int) in.size());
        return in[v];
    }

    int out_time(int v) const {
        assert(v >= 0 && v < (int) out.size());
        return out[v];
    }

    int depth(int v) const {
        assert(v >= 0 && v < (int) dep.size());
        return dep[v];
    }

    int time_to_vertex(int t) const {
        assert(t >= 0 && t < (int) rev.size());
        return rev[t];
    }
    
    int la(int v, int k) const {
        assert(v >= 0 && v < (int) dep.size());
        assert(k >= 0);
        if (k > dep[v]) {
            return -1;
        }
        while (true) {
            int u = hea[v];
            if (in[u] + k <= in[v]) {
                return rev[in[v] - k];
            }
            k -= in[v] - in[u] + 1;
            v = par[u];
        }
        return 0;
    }
    
    int forward(int v, int dst) const {
        assert(v >= 0 && v < (int) dep.size());
        assert(dst >= 0 && dst < (int) dep.size());
        assert(v != dst);
        int l = lca(v, dst);
        if (l == v) {
            return la(dst, dist(v, dst) - 1);
        } else {
            return par[v];
        }
    }

    int lca(int u, int v) const {
        assert(u >= 0 && u < (int) dep.size());
        assert(v >= 0 && v < (int) dep.size());
        while (u != v) {
            if (in[u] > in[v]) {
                std::swap(u, v);
            }
            if (hea[u] == hea[v]) {
                v = u;
            } else {
                v = par[hea[v]];
            }
        }
        return u;
    }

    int dist(int u, int v) const {
        assert(u >= 0 && u < (int) dep.size());
        assert(v >= 0 && v < (int) dep.size());
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }

    std::vector<std::pair<int, int>> path(int u, int v, bool edge) const {
        assert(u >= 0 && u < (int) dep.size());
        assert(v >= 0 && v < (int) dep.size());
        std::vector<std::pair<int, int>> fromu, fromv;
        bool rev = false;
        while (true) {
            if (u == v && edge) {
                break;
            }
            if (in[u] > in[v]) {
                std::swap(u, v);
                std::swap(fromu, fromv);
                rev ^= true;
            }
            if (hea[u] == hea[v]) {
                fromv.emplace_back(in[v], in[u] + (int)edge);
                v = u;
                break;
            } else {
                fromv.emplace_back(in[v], in[hea[v]]);
                v = par[hea[v]];
            }
        }
        if (rev) {
            std::swap(fromu, fromv);
        }
        std::reverse(fromv.begin(), fromv.end());
        fromu.reserve(fromv.size());
        for (auto [x, y] : fromv) {
            fromu.emplace_back(y, x);
        }
        return fromu;
    }
    
    int jump(int u, int v, int k) const {
        assert(u >= 0 && u < (int) dep.size());
        assert(v >= 0 && v < (int) dep.size());
        assert(k >= 0);
        int l = lca(u, v);
        int dis = dep[u] + dep[v] - 2 * dep[l];
        if (k > dis) {
            return -1;
        }
        if (k <= dep[u] - dep[l]) {
            return la(u, k);
        } else {
            return la(v, dis - k);
        }
    }
    
    int meet(int u, int v, int w) const {
        return lca(u, v) ^ lca(v, w) ^ lca(w, u);
    }
};

// ============
// ============

#include <cassert>
#include <utility>
#include <vector>

template <typename MonoidFunc>
class LazySegmentTree {
public:
    using Value = typename MonoidFunc::Value;
    using Func = typename MonoidFunc::Func;

private:
    int old_length;
    int lg;
    int length;
    std::vector<Value> values;
    std::vector<Func> funcs;

    static int lg2(int n) {
        int x = 1;
        int l = 0;
        while (x < n) {
            x <<= 1;
            ++l;
        }
        return l;
    }

    void _apply(int idx, const Func &func) {
        values[idx] = MonoidFunc::apply(func, values[idx]);
        funcs[idx] = MonoidFunc::composite(func, funcs[idx]);
    }

    void push(int idx) {
        _apply(idx << 1, funcs[idx]);
        _apply(idx << 1 | 1, funcs[idx]);
        funcs[idx] = MonoidFunc::func_id();
    }

    void recalc_values(int idx) {
        values[idx] = MonoidFunc::op(values[idx << 1], values[idx << 1 | 1]);
    }

public:
    LazySegmentTree(int n) :
        old_length(n),
        lg(lg2(n)),
        length(1 << lg),
        values(length << 1, MonoidFunc::id()),
        funcs(length << 1, MonoidFunc::func_id()) {
        assert(n >= 0);    
    }

    LazySegmentTree(const std::vector<Value> &v) :
        old_length((int) v.size()),
        lg(lg2(old_length)),
        length(1 << lg),
        values(length << 1, MonoidFunc::id()),
        funcs(length << 1, MonoidFunc::func_id()) {
        for (int i = 0; i < old_length; ++i) {
            values[i + length] = v[i];
        }
        for (int i = length - 1; i > 0; --i) {
            recalc_values(i);
        }
    }

    template <typename F>
    LazySegmentTree(int n, const F &f) :
        old_length(n),
        lg(lg2(n)),
        length(1 << lg),
        values(length << 1, MonoidFunc::id()),
        funcs(length << 1, MonoidFunc::func_id()) {
        for (int i = 0; i < old_length; ++i) {
            values[i + length] = f(i);
        }
        for (int i = length - 1; i > 0; --i) {
            recalc_values(i);
        }
    }

    void update(int idx, Value val) {
        assert(idx >= 0 && idx < old_length);
        idx += length;
        for (int i = lg; i > 0; --i) {
            push(idx >> i);
        }
        values[idx] = std::move(val);
        while (idx >>= 1) {
            recalc_values(idx);
        }
    }

    void apply(int l, int r, const Func &func) {
        assert(l >= 0 && l <= r && r <= old_length);
        if (l == r) {
            return;
        }
        l += length;
        r += length;
        int _l = l;
        int _r = r;
        for (int i = lg; i > 0; --i) {
            push(_l >> i);
            push((_r - 1) >> i);
        }
        while (l < r) {
            if (l & 1) {
                _apply(l++, func);
            }
            if (r & 1) {
                _apply(--r, func);
            }
            l >>= 1;
            r >>= 1;
        }
        for (int i = 1; i <= lg; ++i) {
            if ((_l >> i << i) != _l) {
                recalc_values(_l >> i);
            }
            if ((_r >> i << i) != _r) {
                recalc_values((_r - 1) >> i);
            }
        }
    }

    Value prod(int l, int r) {
        assert(l >= 0 && l <= r && r <= old_length);
        if (l == r) {
            return MonoidFunc::id();
        }
        l += length;
        r += length;
        for (int i = lg; i > 0; --i) {
            push(l >> i);
            push((r - 1) >> i);
        }
        Value lp = MonoidFunc::id();
        Value rp = MonoidFunc::id();
        while (l < r) {
            if (l & 1) {
                lp = MonoidFunc::op(lp, values[l++]);
            }
            if (r & 1) {
                rp = MonoidFunc::op(values[--r], rp);
            }
            l >>= 1;
            r >>= 1;
        }
        return MonoidFunc::op(lp, rp);
    }
    
    Value all_prod() const {
        return values[1];
    }
};

// ============

struct Upd1 {
    using Value = pair<i32, i32>;
    using Func = bool;
    static Value id() {
        return Value(0, 0);
    }
    static Value op(const Value &x, const Value &y) {
        return Value(x.first + y.first, x.second + y.second);
    }
    static Func func_id() {
        return false;
    }
    static Func composite(Func f, Func g) {
        return f || g;
    }
    static Value apply(Func f, const Value &x) {
        if (f) {
            return Value(x.second, x.second);
        } else {
            return x;
        }
    }
};

class RangeChmin {
    i32 n;
    Vec<i32> data;
    
public:
    RangeChmin(i32 n) : n(n), data(2 * n, INF) {}
    
    void range_chmin(i32 l, i32 r, i32 v) {
        l += n;
        r += n;
        while (l < r) {
            if (l % 2 == 1) {
                chmin(data[l++], v);
            }
            if (r % 2 == 1) {
                chmin(data[--r], v);
            }
            l /= 2;
            r /= 2;
        }
    }
    
    i32 at(i32 idx) const {
        i32 ret = INF;
        idx += n;
        while (idx > 0) {
            chmin(ret, data[idx]);
            idx /= 2;
        }
        return ret;
    } 
};

int main() {
    i32 n, m;
    cin >> n >> m;
    Vec<pair<i32, i32>> edges(m);
    for (auto &[u, v] : edges) {
        cin >> u >> v;
        --u;
        --v;
    }
    Vec<i32> r(n - 1);
    REP(i, n - 1) {
        cin >> r[i];
        --r[i];
    }
    
    Vec<i32> is_in(m, 0);
    for (i32 ei : r) {
        is_in[ei] = 1;
    }
    
    Vec<Vec<i32>> tree(n);
    for (i32 ei : r) {
        auto [u, v] = edges[ei];
        tree[u].emplace_back(v);
        tree[v].emplace_back(u);
    }
    HeavyLightDecomposition hld(tree);
    
    LazySegmentTree<Upd1> seg(n, [&](i32) -> Upd1::Value {
        return Upd1::Value(0, 1);
    });
    RangeChmin rc(n);
    
    i32 nxt = 0;
    Vec<i32> ans(m, -1);
    Vec<i32> used(m, 0);
    REP(i, m) {
        if (is_in[i]) {
            auto &[u, v] = edges[i];
            if (hld.depth(u) > hld.depth(v)) {
                swap(u, v);
            }
            if (rc.at(hld.in_time(v)) != INF) {
                continue;
            }
            seg.apply(hld.in_time(v), hld.in_time(v) + 1, true);
            ans[i] = nxt;
            used[nxt++] = 1;
        } else {
            auto [u, v] = edges[i];
            Upd1::Value path = Upd1::id();
            for (auto [l, r] : hld.path(u, v, true)) {
                if (l > r) {
                    swap(l, r);
                }
                path = Upd1::op(path, seg.prod(l, r + 1));
            }
            nxt += path.second - path.first;
            for (auto [l, r] : hld.path(u, v, true)) {
                if (l > r) {
                    swap(l, r);
                }
                rc.range_chmin(l, r + 1, nxt);
                seg.apply(l, r + 1, true);
            }
            ans[i] = nxt;
            used[nxt++] = 1;
        }
    }
    
    Vec<i32> pct;
    for (i32 ei : r) {
        if (ans[ei] == -1) {
            pct.push_back(ei);
        }
    }
    sort(ALL(pct), [&](i32 i, i32 j) -> bool {
        return make_pair(rc.at(hld.in_time(edges[i].second)), i) < make_pair(rc.at(hld.in_time(edges[j].second)), j);
    });
    nxt = 0;
    for (i32 i : pct) {
        while (used[nxt]) {
            ++nxt;
        }
        ans[i] = nxt++;
    }
    
    REP(i, m) {
        cout << ans[i] + 1 << " \n"[i + 1 == m];
    }
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #2
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 14680 KB Output is correct
2 Correct 266 ms 22892 KB Output is correct
3 Correct 379 ms 13192 KB Output is correct
4 Correct 278 ms 46472 KB Output is correct
5 Correct 315 ms 48460 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 256 ms 21084 KB Output is correct
2 Correct 183 ms 11292 KB Output is correct
3 Correct 90 ms 5936 KB Output is correct
4 Correct 180 ms 17936 KB Output is correct
5 Correct 58 ms 6988 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 400 ms 40204 KB Output is correct
2 Correct 451 ms 50368 KB Output is correct
3 Correct 94 ms 15264 KB Output is correct
4 Correct 117 ms 21536 KB Output is correct
5 Correct 467 ms 58324 KB Output is correct

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 263 ms 28840 KB Output is correct
2 Correct 132 ms 21092 KB Output is correct
3 Correct 466 ms 51144 KB Output is correct
4 Correct 401 ms 44020 KB Output is correct
5 Correct 28 ms 4484 KB Output is correct

Subtask #7
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 99 ms 14680 KB Output is correct
10 Correct 266 ms 22892 KB Output is correct
11 Correct 379 ms 13192 KB Output is correct
12 Correct 278 ms 46472 KB Output is correct
13 Correct 315 ms 48460 KB Output is correct
14 Correct 256 ms 21084 KB Output is correct
15 Correct 183 ms 11292 KB Output is correct
16 Correct 90 ms 5936 KB Output is correct
17 Correct 180 ms 17936 KB Output is correct
18 Correct 58 ms 6988 KB Output is correct
19 Correct 400 ms 40204 KB Output is correct
20 Correct 451 ms 50368 KB Output is correct
21 Correct 94 ms 15264 KB Output is correct
22 Correct 117 ms 21536 KB Output is correct
23 Correct 467 ms 58324 KB Output is correct
24 Correct 263 ms 28840 KB Output is correct
25 Correct 132 ms 21092 KB Output is correct
26 Correct 466 ms 51144 KB Output is correct
27 Correct 401 ms 44020 KB Output is correct
28 Correct 28 ms 4484 KB Output is correct
29 Correct 705 ms 44100 KB Output is correct
30 Correct 647 ms 45264 KB Output is correct
31 Correct 552 ms 48324 KB Output is correct
32 Correct 440 ms 12680 KB Output is correct
33 Correct 486 ms 48668 KB Output is correct