Submission #671197

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
671197	2022-12-12T11:45:08 Z	Forested	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	705 ms	58324 KB

riggedroads

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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