제출 #1210044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210044		Fatonim	Vinjete (COI22_vinjete)	C++20	69 / 100	175 ms	78440 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 = 1e5 + 7;
/////////////////////////solve/////////////////////////

struct node {
    int mn = 0, cnt = 0, add = 0;
    int l = -1, r = -1;
};

int tim = 1;
node tree[maxn * 34];

int newnode(int tl, int tr) {
    tree[tim].cnt = tr - tl;
    return tim++;
}

void apply(int v, int tl, int tr, int x) {
    tree[v].mn += x;
    tree[v].add += x;
}

void push(int v, int tl, int tr) {
    int tm = (tl + tr) >> 1;
    if (tree[v].l == -1) {
        tree[v].l = newnode(tl, tm);
        tree[v].r = newnode(tm, tr);
    }
    if (tree[v].add != 0) {
        apply(tree[v].l, tl, tm, tree[v].add);
        apply(tree[v].r, tm, tr, tree[v].add);
        tree[v].add = 0;
    }
}

void pull(int v, int tl, int tr) {
    int lv = tree[v].l, rv = tree[v].r;
    tree[v].mn = min(tree[lv].mn, tree[rv].mn);
    tree[v].cnt = 0;
    if (tree[v].mn == tree[lv].mn) tree[v].cnt += tree[lv].cnt;
    if (tree[v].mn == tree[rv].mn) tree[v].cnt += tree[rv].cnt;
}

void update(int l, int r, int x, int v, int tl, int tr) {
    if (tl >= r || tr <= l) return;
    if (tl >= l && tr <= r) {
        apply(v, tl, tr, x);
        return;
    }
    push(v, tl, tr);
    int tm = (tl + tr) >> 1;
    update(l, r, x, tree[v].l, tl, tm);
    update(l, r, x, tree[v].r, tm, tr);
    pull(v, tl, tr);
}

int rt;
int get() {
    return (tree[rt].mn == 0 ? tree[rt].cnt : 0);
}

vector<pair<int, pi>> g[maxn];
int ans[maxn];
int n, m;

void dfs(int v, int p = -1) {
    ans[v] = m - get();
    for (auto [u, seg] : g[v]) {
        if (u != p) {
            auto [l, r] = seg;
            update(l, r + 1, 1, rt, 0, m);
            dfs(u, v);
            update(l, r + 1, -1, rt, 0, m);
        }
    }
}

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}});
    }

    rt = newnode(0, 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: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 29 / 29
• Subtask 5: 0 / 31