Submission #752152

#TimeUsernameProblemLanguageResultExecution timeMemory
752152Dan4LifeConstruction of Highway (JOI18_construction)C++17
100 / 100
1500 ms106740 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define all(a) begin(a),end(a) const int N = (int)1e5+2; using ll = long long; using ar = array<int,2>; vector<int> adj[N]; deque<ar> ch[N], edge; int n, c[N], h[N], sub[N], p[N], dep[N], fen[N]; void upd(int x, int v){ for(; x<N; x+=x&-x) fen[x]+=v; } int sum(int x){ int s=0; for(; x; x-=x&-x) s+=fen[x]; return s; } int dfsSz(int s, int par){ sub[s] = 1; p[s] = par; for(auto &u : adj[s]){ if(u==par) continue; int x = adj[s][0]; dep[u] = dep[s]+1, sub[s]+=dfsSz(u,s); if(sub[x]<sub[u]) swap(adj[s][0],u); } return sub[s]; } void Hld(int s, int par, int head){ h[s] = head; for(auto u : adj[s]) if(u!=par) Hld(u,s,u==adj[s][0]?head:u); } ll calc(int a){ vector<ar> v, tv; v.clear(); ll ans = 0; while(a!=-1){ int H = h[a], siz = dep[a]-dep[h[a]]+1; tv.clear(); for(auto [x,cnt] : ch[H]){ tv.pb({x,min(cnt,siz)}), siz-=min(cnt,siz); if(!siz) break; } a = p[H]; reverse(all(tv)); for(auto u : tv) v.pb(u); } for(int i = 1; i <= n; i++) fen[i]=0; for(auto [x,y] : v) ans+=(ll)y*sum(x-1), upd(x,y); return ans; } void add(int b, int v){ while(b!=-1){ int H = h[b], siz = dep[b]-dep[h[b]]+1; int tsz = siz; while(!ch[H].empty() and siz){ int cnt = ch[H].front()[1]; if(cnt<=siz) ch[H].pop_front(), siz-=cnt; else ch[H].front()[1]-=siz, siz=0; } ch[H].push_front({v,tsz}); b = p[H]; } } int main() { ios_base::sync_with_stdio(false); cin.tie(); cin >> n; vector<int> v; int a, b; for(int i = 1; i <= n; i++) cin >> c[i], v.pb(c[i]); sort(all(v)), v.erase(unique(all(v)),end(v)); for(int i = 1; i <= n; i++) c[i] = lower_bound(all(v),c[i])-begin(v)+1; for(int i = 1; i < n; i++) cin >> a >> b, adj[a].pb(b), edge.pb({a,b}); ch[1].pb({c[1],1}); dfsSz(1,-1); Hld(1,-1,1); for(auto [a,b] : edge) cout << calc(a) << "\n", add(b,c[b]); }

Compilation message (stderr)

construction.cpp: In function 'int dfsSz(int, int)':
construction.cpp:18:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   18 |   if(u==par) continue; int x = adj[s][0];
      |   ^~
construction.cpp:18:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   18 |   if(u==par) continue; int x = adj[s][0];
      |                        ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...