제출 #953480

#제출 시각아이디문제언어결과실행 시간메모리
953480tnknguyen_Vinjete (COI22_vinjete)C++14
27 / 100
104 ms66840 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define pii pair<int, int> const int MX = 1e5 + 5; vector<pair<int, pii>> gr[MX]; int L[MX], R[MX], f[MX]; int ans[MX]; struct node{ int good, sum; node(){ good = sum = 0; } }; struct SMT{ vector<node> tree; int n = 1e5 + 5; SMT(){ tree.assign(4*n + 5, node()); }; void update(int id, int l, int r, int u, int v, int val){ if(r < u || l > v){ return; } if(u <=l && r <= v){ tree[id].good += val; tree[id].sum = (tree[id].good ? r-l+1 : tree[2*id].sum + tree[2*id+1].sum); return; } int mid = (l + r) >> 1, ID = (id << 1); update(ID, l, mid, u, v, val); update(ID|1, mid+1, r, u, v, val); tree[id].sum = (tree[id].good ? r-l+1 : tree[ID].sum + tree[ID|1].sum); } void update(int l, int r, int val){ update(1, 1, n, l, r, val); } int get(int id, int l, int r, int u, int v){ if(r < u || l > v){ return 0; } if(u <= l && r <= v){ return tree[id].sum; } int mid = (l + r) >> 1, ID = (id << 1); return get(ID, l, mid, u, v) + get(ID|1, mid+1, r, u, v); } }; SMT smt; void dfs(int u, int p){ ans[u] = smt.tree[1].sum; for(pair<int, pii> e : gr[u]){ int v, l, r; v = e.first; tie(l, r) = e.second; if(v != p){ smt.update(l, r, 1); dfs(v, u); smt.update(l, r, -1); } } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("main.inp","r",stdin); //freopen("main.out","w",stdout); int n, m; cin>>n>>m; for(int i=1; i<n; ++i){ int u, v, l, r; cin>>u>>v>>l>>r; gr[u].push_back({v, {l, r}}); gr[v].push_back({u, {l, r}}); } dfs(1, 0); for(int i=2; i<=n; ++i){ cout<<ans[i]<<endl; } 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...