Submission #1128991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128991		gyg	Vinjete (COI22_vinjete)	C++20	100 / 100	800 ms	207800 KiB

Main

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

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

struct Sg {
    struct Nd { int mn, cnt, lzy; };
    int nm_nds = 1;
    arr<Nd, 4 * N * LG_K> sg;
    arr<int, 4 * N * LG_K> lf, rg;
    
    void prp(int u, int lw, int hg) {
        if (!lf[u]) {
            int md = (lw + hg) / 2;
            lf[u] = ++nm_nds, sg[nm_nds] = {0, md - lw + 1, 0};
            rg[u] = ++nm_nds, sg[nm_nds] = {0, hg - md, 0};
        }
        for (int v : {lf[u], rg[u]})
            sg[v].mn += sg[u].lzy, sg[v].lzy += sg[u].lzy;
        sg[u].lzy = 0;
    }
    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 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, lw, hg);
        int md = (lw + hg) / 2;
        upd(l, r, x, lf[u], lw, md), upd(l, r, x, rg[u], md + 1, hg);
        sg[u] = mrg(sg[lf[u]], sg[rg[u]]);
    }
    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});
    }
    dfs();
    for (int u = 2; u <= n; u++) cout << ans[u] << endl;
}

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