Submission #850593

#	Time	Username	Problem	Language	Result	Execution time	Memory
850593		Cyanmond	Vinjete (COI22_vinjete)	C++17	100 / 100	193 ms	35468 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= l; --i)
#define ALL(x) (x).begin(), (x).end()

using i64 = long long;

struct Node {
    i64 len;
    i64 sum;
    i64 cnt;
};

void merge(Node &p, Node &a, Node &b) {
    p.len = a.len + b.len;
    p.sum = (a.cnt >= 1 ? a.len : a.sum) + (b.cnt >= 1 ? b.len : b.sum);
}

void ap(Node &nd, int v) {
    nd.cnt += v;
    
}

Node id() {
    return {0, 0, 0};
}

struct UnionSeg {
    int n, siz, lg;
    vector<Node> data;

    UnionSeg(int n_) : n(n_) {
        lg = 0;
        while ((1 << lg) < n) ++lg;
        siz = 1 << lg;
        data.assign(2 * siz, id());
    }

    void affine(int i, const Node &nd) {
        i += siz;
        data[i] = nd;
        while (i != 1) {
            i /= 2;
            merge(data[i], data[2 * i], data[2 * i + 1]);
        }
    }

    void apply(int l, int r, int v) {
        l += siz, r += siz;
        int l2 = l, r2 = r;
        for (; l < r; l /= 2, r /= 2) {
            if (l & 1) {
                data[l].cnt += v;
                ++l;
            }
            if (r & 1) {
                --r;
                data[r].cnt += v;
            }
        }
        l = l2, r = r2;
        for (int i = 1; i <= lg; ++i) {
            merge(data[l >> i], data[2 * (l >> i)], data[2 * (l >> i) + 1]);
            merge(data[(r - 1) >> i], data[2 * ((r - 1) >> i)], data[2 * ((r - 1) >> i) + 1]);
        }
    }

    i64 sum() {
        return data[1].cnt >= 1 ? data[1].len : data[1].sum;
    }
};

void main_() {
    int N;
    i64 M;
    cin >> N >> M;
    vector<vector<tuple<int, i64, i64>>> Tree(N);
    vector<i64> vals;
    rep(i, 0, N - 1) {
        int a, b, l, r;
        cin >> a >> b >> l >> r;
        --a, --b;
        --l;
        Tree[a].push_back({b, l, r});
        Tree[b].push_back({a, l, r});
        vals.push_back(l);
        vals.push_back(r);
    }
    sort(ALL(vals));
    vals.erase(unique(ALL(vals)), vals.end());

    const int X = (int)vals.size();
    UnionSeg seg(X - 1);
    rep(i, 0, X - 1) {
        seg.affine(i, {vals[i + 1] - vals[i], 0, 0});
    }

    vector<i64> ans(N);
    auto dfs = [&](auto &&self, const int v, const int p) -> void {
        ans[v] = seg.sum();
        for (const auto &[t, l, r] : Tree[v]) {
            if (t == p) continue;
            const int a = (int)(lower_bound(ALL(vals), l) - vals.begin());
            const int b = (int)(lower_bound(ALL(vals), r) - vals.begin());
            seg.apply(a, b, 1);
            self(self, t, v);
            seg.apply(a, b, -1);
        }
    };
    dfs(dfs, 0, -1);

    rep(i, 1, N) cout << ans[i] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    main_();
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31