Submission #850725

#TimeUsernameProblemLanguageResultExecution timeMemory
850725TahirAliyevVinjete (COI22_vinjete)C++17
69 / 100
303 ms187984 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define ll long long int #define oo 2e9 #define pii pair<ll, int> const int MAX = 1e5 + 5, LOGMAX = 31, treesize = MAX * LOGMAX; int n, m; vector<array<int, 3>> g[MAX]; pii tree[treesize]; int L[treesize], R[treesize], lazy[treesize]; int nxt = 2; void relax(int node, int l, int r){ if(!lazy[node]) return; tree[node].first += lazy[node]; if(l == r){ lazy[node] = 0; return; } int mid = (l + r) / 2; if(!L[node]){ L[node] = nxt++; tree[L[node]] = {0, mid - l + 1}; } if(!R[node]){ R[node] = nxt++; tree[R[node]] = {0, r - mid}; } lazy[L[node]] += lazy[node]; lazy[R[node]] += lazy[node]; lazy[node] = 0; } pii combine(pii a, pii b){ if(a.first == b.first){ return {a.first, a.second + b.second}; } return min(a, b); } void update(int node, int l, int r, int ul, int ur, int val){ relax(node, l, r); if(ur < l || r < ul) return; if(ul <= l && r <= ur){ lazy[node] += val; relax(node, l, r); return; } int mid = (l + r) / 2; if(!L[node]){ L[node] = nxt++; tree[L[node]] = {0, mid - l + 1}; } if(!R[node]){ R[node] = nxt++; tree[R[node]] = {0, r - mid}; } update(L[node], l, mid, ul, ur, val); update(R[node], mid + 1, r, ul, ur, val); tree[node] = combine(tree[L[node]], tree[R[node]]); } int ans[MAX]; void dfs(int node, int p, int l, int r){ if(node != 1){ update(1, 1, m, l, r, 1); } if(tree[1].first == 0){ ans[node] = m - tree[1].second; } else{ ans[node] = m; } for(auto to : g[node]){ if(p == to[0]) continue; dfs(to[0], node, to[1], to[2]); } if(node != 1){ update(1, 1, m, l, r, -1); } } int main(){ cin >> n >> m; for(int i = 1; i < n; i++){ int a, b, l, r; cin >> a >> b >> l >> r; g[a].push_back({b, l, r}); g[b].push_back({a, l, r}); } tree[1] = {0, m}; dfs(1, 1, 0, 0); for(int i = 2; i <= n; i++){ cout << ans[i] << '\n'; } }
#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...