제출 #1210198

#제출 시각아이디문제언어결과실행 시간메모리
1210198bakhtiyarnVinjete (COI22_vinjete)C++20
0 / 100
18 ms7516 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5+5; const int N2 = 1e5+1; vector<array<int, 3>> g[N2]; int ans[N2]; int n, M; int nxt = 1; unordered_map<int, int> L, R, sg; unordered_map<int, bool> lz; void push(int u, int l, int r, int U, unordered_map<int, int> &usedsg, unordered_map<int, bool> &usedlz){ if(lz[u]) { if(!usedsg[u]) usedsg[u] = sg[u]; sg[u] = r-l+1; } if(l != r){ if(!L[u]) L[u] = ++nxt; if(!R[u]) R[u] = ++nxt; if(L[u]) { if(!usedlz[L[u]]) usedlz[L[u]] = lz[L[u]]; lz[L[u]] += lz[u]; } if(R[u]) { if(!usedlz[R[u]]) usedlz[R[u]] = lz[R[u]]; lz[R[u]] += lz[u]; } if(l == 1 and r == 3 and U == 3){ // cout << lz[R[u]] << endl; } } } void update(int u, int l, int r, int x, int y, int U, unordered_map<int, int> &usedsg, unordered_map<int, bool> &usedlz){ push(u, l, r, U, usedsg, usedlz); if(y < l or x > r) return; if(x <= l and y >= r){ if(!usedlz[u]) usedlz[u] = lz[u]; lz[u] = true; push(u, l, r, U, usedsg, usedlz); return; } /// int m = (l+r)/2; int add = 0; if(y < l or x > m) { if(L[u]) push(L[u], l, m, U, usedsg, usedlz); } else { if(!L[u]) L[u] = ++nxt; push(u, l, r, U, usedsg, usedlz); update(L[u], l, m, x, y, U, usedsg, usedlz); } if(y < m+1 or x > r) { if(R[u]) push(R[u], m+1, r, U, usedsg, usedlz); } else { if(!R[u]) R[u] = ++nxt; push(u, l, r, U, usedsg, usedlz); update(R[u], m+1, r, x, y, U, usedsg, usedlz); } /// if(!usedsg[u]) usedsg[u] = sg[u]; int sol = 0, sag = 0; if(L[u]) sol = L[u]; if(R[u]) sag = R[u]; sg[u] = sg[sol] + sg[sag] + add; // if(lz[u]) sg[u] = r-l+1; } void dfs(int u, int p, int li, int ri){ unordered_map<int, int> usedsg; unordered_map<int, bool> usedlz; update(1, 1, M, li, ri, u, usedsg, usedlz); ans[u] = sg[1]; for(auto [to, lj, rj]: g[u]){ if(to == p) continue; dfs(to, u, lj, rj); } for(auto [node, ans]: usedsg) sg[node] = ans; for(auto [node, ans]: usedlz) lz[node] = ans; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> M; for(int i=1; i<n; i++){ int x, y, li, ri; cin >> x >> y >> li >> ri; g[x].push_back({y, li, ri}); g[y].push_back({x, li, ri}); } 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...