제출 #1210211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210211		bakhtiyarn	Vinjete (COI22_vinjete)	C++20	0 / 100	4 ms	3144 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long

template<typename K, typename V>
using hash_table = gp_hash_table<K, V>;

const int N = 1e5 + 5;
int n, M;
vector<array<int, 3>> g[N];
int ans[N];

hash_table<int, int> L, R, lz, sg;
vector<array<int, 2>> chsg, chlz;
int nxt = 1;

void push(int u, int l, int r) {
    if (lz[u] == 0) return;

    if (sg.find(u) == sg.end()) chsg.push_back({u, 0});
    else chsg.push_back({u, sg[u]});

    sg[u] = r - l + 1;

    if (l != r) {
        int m = (l + r) / 2;
        if (!L[u]) L[u] = ++nxt;
        if (!R[u]) R[u] = ++nxt;

        if (lz.find(L[u]) == lz.end()) chlz.push_back({L[u], 0});
        else chlz.push_back({L[u], lz[L[u]]});
        if (lz.find(R[u]) == lz.end()) chlz.push_back({R[u], 0});
        else chlz.push_back({R[u], lz[R[u]]});

        lz[L[u]] += lz[u];
        lz[R[u]] += lz[u];
    }

    lz[u] = 0;
}

void update(int u, int l, int r, int x, int y) {
    push(u, l, r);
    if (r < x || y < l) return;

    if (x <= l && r <= y) {
        if (lz.find(u) == lz.end()) chlz.push_back({u, 0});
        else chlz.push_back({u, lz[u]});
        lz[u]++;
        push(u, l, r);
        return;
    }

    int m = (l + r) / 2;
    if (!L[u]) L[u] = ++nxt;
    if (!R[u]) R[u] = ++nxt;

    update(L[u], l, m, x, y);
    update(R[u], m + 1, r, x, y);

    if (sg.find(u) == sg.end()) chsg.push_back({u, 0});
    else chsg.push_back({u, sg[u]});
    sg[u] = sg[L[u]] + sg[R[u]];
}

void dfs(int u, int p, int li, int ri) {
    chsg.clear();
    chlz.clear();

    if (li && ri) update(1, 1, M, li, ri);
    ans[u] = sg[1];

    for (auto [v, l, r] : g[u]) {
        if (v == p) continue;
        dfs(v, u, l, r);
    }

    for (int i = chsg.size() - 1; i >= 0; --i) {
        auto [x, val] = chsg[i];
        sg[x] = val;
    }

    for (int i = chlz.size() - 1; i >= 0; --i) {
        auto [x, val] = chlz[i];
        lz[x] = val;
    }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n >> M;
    for (int i = 1; i < n; ++i) {
        int u, v, l, r;
        cin >> u >> v >> l >> r;
        g[u].push_back({v, l, r});
        g[v].push_back({u, l, r});
    }

    dfs(1, -1, 0, 0);

    for (int i = 2; i <= n; ++i)
        cout << ans[i] << '\n';
}

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