Submission #1052169

#TimeUsernameProblemLanguageResultExecution timeMemory
1052169VMaksimoski008Vinjete (COI22_vinjete)C++17
100 / 100
519 ms119072 KiB
#include <bits/stdc++.h> //#define int long long using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; const int mod = 1e9 + 7; const int LOG = 20; const int maxn = 1e5 + 5; const int seg_sz = 5e6+5; struct SegTree { int n, id=2; vector<pii> tree; vector<int> lazy, L, R; SegTree(int _n) : n(_n), tree(seg_sz), lazy(seg_sz), L(seg_sz), R(seg_sz) { tree[1] = { 0, n }; } void init(int n2) { n = n2; tree[1] = { 0, n }; } pii merge(pii a, pii b) { if(a.first < b.first) return a; if(a.first > b.first) return b; return { a.first, a.second + b.second }; } void push(int u, int tl, int tr) { if(!lazy[u]) return ; tree[u].first += lazy[u]; if(tl != tr) { if(L[u]) lazy[L[u]] += lazy[u]; if(R[u]) lazy[R[u]] += lazy[u]; } lazy[u] = 0; } void update(int u, int tl, int tr, int l, int r, int v) { push(u, tl, tr); if(tl > tr || l > tr || tl > r) return ; if(l <= tl && tr <= r) { lazy[u] += v; push(u, tl, tr); return ; } int tm = (tl + tr) / 2; if(L[u]) update(L[u], tl, tm, l, r, v); if(R[u]) update(R[u], tm+1, tr, l, r, v); tree[u] = merge(tree[L[u]], tree[R[u]]); } void add(int u, int tl, int tr, int l, int r) { if(tl > tr || l > tr || tl > r) return ; if(l <= tl && tr <= r) return ; int tm = (tl + tr) / 2; if(L[u] == 0) { L[u] = id++; tree[L[u]] = { tree[u].first, tm - tl + 1 }; } if(R[u] == 0) { R[u] = id++; tree[R[u]] = { tree[u].first, tr - tm }; } add(L[u], tl, tm, l, r); add(R[u], tm+1, tr, l, r); } pii query() { push(1, 1, n); return tree[1]; } void update(int l, int r, int v) { add(1, 1, n, l, r); update(1, 1, n, l, r, v); } } tree(1e9); int m; vector<array<int, 3> > graph[maxn]; vector<int> ans(maxn); void dfs(int u, int p) { if(tree.query().first == 0) ans[u] = m - tree.query().second; else ans[u] = m; for(auto &[v, l, r] : graph[u]) { if(v == p) continue; tree.update(l, r, 1); dfs(v, u); tree.update(l, r, -1); } } signed main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); int n; cin >> n >> m; tree.init(m); for(int i=0; i<n-1; i++) { int a, b, l, r; cin >> a >> b >> l >> r; graph[a].push_back({ b, l, r }); graph[b].push_back({ a, l, r }); } dfs(1, 1); for(int i=2; i<=n; i++) cout << ans[i] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...