Submission #752147

#	Time	Username	Problem	Language	Result	Execution time	Memory
752147		Dan4Life	Construction of Highway (JOI18_construction)	C++17	100 / 100	1600 ms	108808 KiB

construction

#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; v.clear(); ll ans = 0;
	while(a!=-1){
		int H = h[a], siz = dep[a]-dep[h[a]]+1;
		vector<ar> tv; tv.clear();
		for(auto [x,cnt] : ch[H]){
			tv.pb({x,min(cnt,siz)}), siz-=min(cnt,siz);
			if(!siz) break;
		}
		reverse(all(tv)); for(auto u : tv) v.pb(u);
		a = p[H];
	}
	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 addEdge(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];
	}
}

int32_t 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", addEdge(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];
      |                        ^~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84