Submission #1209452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209452		Fatonim	Vinjete (COI22_vinjete)	C++20	56 / 100	175 ms	39380 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#ifdef ONPC
#include "debug.h"
#else
#define dbg(...)
#endif

#define ll long long
#define int long long
#define ld long double
#define pi pair<int, int>
#define sz(a) ((int)(a.size()))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sqr(n) ((n) * (n))
#define divup(a, b) (((a) + (b)-1) / (b))
#define popcount(n) __builtin_popcountll(n)
#define clz(n) __builtin_clzll(n)
#define Fixed(a) cout << fixed << setprecision(12) << a;

template <class T> bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool chmax(T& a, const T& b) { return b > a ? a = b, 1 : 0; }

const int mod = 998244353; // 998244353 1e9 + 7
const ll inf = (ll)(1e18) + 7;
const ld eps = 1e-9;

const int B = 32;
const int N = 1000 + 3;
const int logn = 20;
const int maxn = 2e5 + 7;
/////////////////////////solve/////////////////////////

struct segtree {
public:
    struct node {
        int mn = 0;
        int cnt = 0;
        int add = 0;
        void apply(int tl, int tr, int x) {
            mn += x;
            add += x;
        }
    };
private:
    int n;
    vector<node> tree;

    node unite(const node& a, const node& b) {
        node res;
        res.mn = min(a.mn, b.mn);
        if (res.mn == a.mn) res.cnt += a.cnt;
        if (res.mn == b.mn) res.cnt += b.cnt;
        return res;
    }

    void push(int v, int tl, int tr) {
        int tm = (tl + tr) >> 1;

        if (tree[v].add != 0) {
            tree[2 * v].apply(tl, tm, tree[v].add);
            tree[2 * v + 1].apply(tm, tr, tree[v].add);
            tree[v].add = 0;
        }
    }

    template <class T>
    void build(const vector<T>& a, int v, int tl, int tr) {
        if (tr - tl == 1) {
            tree[v].apply(tl, tr, a[tl]);
            return;
        }
        int tm = (tl + tr) >> 1;
        build(a, 2 * v, tl, tm);
        build(a, 2 * v + 1, tm, tr);
        tree[v] = unite(tree[2 * v], tree[2 * v + 1]);
    }

    void build(int v, int tl, int tr) {
        if (tr - tl == 1) {
            tree[v].cnt = 1;
            return;
        }
        int tm = (tl + tr) >> 1;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm, tr);
        tree[v] = unite(tree[2 * v], tree[2 * v + 1]);
    }

    template <class T>
    void update(int l, int r, const T& x, int v, int tl, int tr) {
        if (tl >= r || tr <= l) return;
        if (tl >= l && tr <= r) {
            tree[v].apply(tl, tr, x);
            return;
        }
        int tm = (tl + tr) >> 1;
        push(v, tl, tr);
        update(l, r, x, 2 * v, tl, tm);
        update(l, r, x, 2 * v + 1, tm, tr);
        tree[v] = unite(tree[2 * v], tree[2 * v + 1]);
    }

    node get(int l, int r, int v, int tl, int tr) {
        if (tl >= l && tr <= r) return tree[v];
        int tm = (tl + tr) >> 1;
        push(v, tl, tr);
        if (tm <= l) return get(l, r, 2 * v + 1, tm, tr);
        if (tm >= r) return get(l, r, 2 * v, tl, tm);
        return unite(get(l, r, 2 * v, tl, tm),
            get(l, r, 2 * v + 1, tm, tr));
    }

public:
    segtree(int n) : n(n) {
        tree.resize(4 * n);
        build(1, 0, n);
    }

    template <class T>
    segtree(const vector<T>& a) {
        n = sz(a);
        tree.resize(4 * n);
        build(a, 1, 0, n);
    }

    template <class T>
    void update(int l, int r, const T& x) {
        update(l, r, x, 1, 0, n);
    }

    template <class T>
    void update(int i, const T& x) {
        update(i, i + 1, x, 1, 0, n);
    }

    node get(int l, int r) {
        return get(l, r, 1, 0, n);
    }

    node get(int i) {
        return get(i, i + 1, 1, 0, n);
    }
};

vector<pair<int, pi>> g[maxn];
segtree st(1);
int ans[maxn];
int n, m;

void dfs(int v, int p = -1) {
    segtree::node cur = st.get(0, m);
    int cnt = 0;
    if (cur.mn == 0) cnt = cur.cnt;
    ans[v] = m - cnt;
    // dbg(cur.mn, cnt);
    for (auto [u, seg] : g[v]) {
        if (u != p) {
            auto [l, r] = seg;
            st.update(l, r + 1, 1);
            dfs(u, v);
            st.update(l, r + 1, -1);
        }
    }
}

void solve() {
    cin >> n >> m;

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

    st = segtree(m);
    dfs(0);
    for (int i = 1; i < n; ++i) {
        cout << ans[i] << "\n";
    }
}

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

#ifdef ONPC
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif

    solve();
}

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