Submission #1128987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128987		gyg	Vinjete (COI22_vinjete)	C++20	56 / 100	375 ms	82388 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define arr array 
#define vec vector
const int N = 1e5 + 5, K = 1e5 + 5;

int n, k;
arr<vec<vec<int>>, N> adj;

struct Sg {
    struct Nd { int mn, cnt, lzy; };
    arr<Nd, 4 * K> sg;
    
    Nd mrg(Nd x, Nd y) {
        if (x.mn > y.mn) swap(x, y);
        Nd ans = {x.mn, (x.mn == y.mn) ? x.cnt + y.cnt : x.cnt, 0};
        return ans;
    }
    void bld(int u = 1, int lw = 1, int hg = k) {
        if (lw == hg) { sg[u] = {0, 1, 0}; return; }
        int md = (lw + hg) / 2;
        bld(2 * u, lw, md), bld(2 * u + 1, md + 1, hg);
        sg[u] = mrg(sg[2 * u], sg[2 * u + 1]);
    }
    void prp(int u) {
        for (int v : {2 * u, 2 * u + 1})
            sg[v].mn += sg[u].lzy, sg[v].lzy += sg[u].lzy;
        sg[u].lzy = 0;
    }
    void upd(int l, int r, int x, int u = 1, int lw = 1, int hg = k) {
        if (r < lw || hg < l) return;
        if (l <= lw && hg <= r) { sg[u].mn += x, sg[u].lzy += x; return; }
        prp(u);
        int md = (lw + hg) / 2;
        upd(l, r, x, 2 * u, lw, md), upd(l, r, x, 2 * u + 1, md + 1, hg);
        sg[u] = mrg(sg[2 * u], sg[2 * u + 1]);
    }
    Nd tp() { return sg[1]; }
} sg;

arr<bool, N> vs;
arr<int, N> ans;
void dfs(int u = 1) {
    vs[u] = true;
    // cout << u << ": " << sg.tp().mn << " " << sg.tp().cnt << endl;
    ans[u] = (sg.tp().mn == 0) ? k - sg.tp().cnt : k;
    for (vec<int> x : adj[u]) {
        if (vs[x[0]]) continue;
        sg.upd(x[1], x[2], +1);
        dfs(x[0]);
        sg.upd(x[1], x[2], -1);
    }
}

signed main() {
    // freopen("a.in", "r", stdin);
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v, l, r; cin >> u >> v >> l >> r;
        adj[u].push_back({v, l, r}), adj[v].push_back({u, l, r});
    }
    sg.bld();
    dfs();
    for (int u = 2; u <= n; u++) cout << ans[u] << endl;
}

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