Submission #1172761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172761		Nurislam	Construction of Highway (JOI18_construction)	C++20	0 / 100	12 ms	24752 KiB

construction

#include <bits/stdc++.h>

using namespace std;


#define int long long
//#define pb push_back

int inf = 1e18; 

const int mod = 1e9 + 7;
const int N = 1e5 + 5;

struct bitt {
	vector<int> t;
	int n;
	bitt (int N) : n(N+1) {
		t.resize(n+2);
	};
	
	void upd(int i, int va) { i ++ ;
		for(; i < n; i += (i & -i)) t[i] += va;
	};
	
	int get(int i) { i ++ ;
		int res = 0;
		for(; i > 0; i -= (i & -i)) res += t[i];
		return res;
	};
	
	int get(int l, int r) { r--;
		return get(r ) - get( -- l );
	};
}bt(N);

struct segt {
	vector<int> t, b;
	int n;
	segt (int N) : n(N+3) {
		t.resize(n);
		b.resize(n*4);
	};
	
	void push(int i, int l, int r) {
		if(b[i] == 0)return;
		if(l == r) t[l] = b[i];
		else{
			b[i << 1] = b[i];
			b[i << 1 | 1] = b[i];
		};
		b[i] = 0;
	};
	
	void upd(int tl, int tr, int va, int i, int l, int r) {
		push(i, l, r);
		if(l > tr || r < tl) return;
		if(tl <= l && r <= tr) {
			b[i] = va;
			push(i, l, r);
			return;
		};
		
		int m = (l + r) >> 1;
		upd(tl, tr, va, i << 1, l, m);
		upd(tl, tr, va, i << 1 | 1, m + 1, r);
	};
	
	void upd(int l, int r, int va) {
		upd(l, r, va, 1, 1, n);
	};
	
	int get(int ps, int i, int l, int r) {
		push(i,l,r);
		if(l == r) return t[l];
		int m = (l + r) >> 1;
		if(ps <= m) return get(ps, i << 1, l, m);
		else return get(ps, i << 1 | 1, m + 1, r);
	};
	
	int get(int ps) {
		return get(ps, 1, 1, n);
	};
}t(N);

vector<vector<int>> g(N);

int sz[N], pr[N], head[N], heavy[N], dep[N], id[N];
int tim = 1;
int ls[22][N];

void dfs(int ps, int par) {
	sz[ps] = 1;
	pr[ps] = par;
	heavy[ps] = 0;
	ls[0][ps] = par;
	for(int i = 1; i < 22; i ++ ) 
		ls[i][ps] = ls[i-1][ls[i-1][ps]];
	
	for(int to : g[ps]) {
		if(to == par)continue;
		dep[to] = dep[ps] + 1;
		dfs(to, ps);
		sz[ps] += sz[to];
		if(sz[heavy[ps]] < sz[to]) heavy[ps] = to;
	}
}

void hld(int ps, int hd) {
	head[ps] = hd;
	id[ps] = tim ++ ;
	
	if(heavy[ps])
		hld(heavy[ps], hd);
		
	for(int to : g[ps]){
		if(to == pr[ps] || to == heavy[ps])continue;
		hld(to, to);
	}
};


int query(int ps) {
	vector<array<int,2>> updates;
	int ans = 0;
	while(1) {
		int to = ps, curv = t.get(id[ps]);
		for(int i = 21; i >= 0; i -- ) {
			int r = ls[i][to];
			if(t.get(id[r]) != curv)continue;
			to = r;
		}
		int cnt = dep[ps] - dep[to] + 1;
		//cout << ps << ' ' << to << ' ' << curv << ' ' << cnt << '\n';
		ans += bt.get(curv - 1) * cnt;
		bt.upd(curv, cnt);
		updates.push_back({curv, cnt});
		if(to == 1)break;
		ps = pr[to];
	};
	for(auto [a, b] : updates) bt.upd(a, -b);
	return ans;
};

void upd (int ps, int va) {
	while(1) {
		t.upd(id[head[ps]], id[ps], va);
		//cout << ps << ' ' << head[ps] << '\n';
		
		if(head[ps] == 1)return;
		ps = pr[head[ps]];
	}
};


void solve(){
	int n; cin >> n;
	
	vector<int> a(n+1);
	for(int i = 1; i <= n; i++ )cin >> a[i];
	
	vector<int> b = a;
	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	for(int i = 1; i <= n; i ++ )a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
	
	vector<array<int,2>> ed(n-1);
	for(auto &[a, b] : ed) {
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	for(auto &i : ls) for(auto &j : i)j = 1;
	
	dfs(1, 1);
	hld(1, 1);
	
	for(int i = 1; i <= n; i ++ ) t.upd(id[i], id[i], a[i]);
	
	//for(int i = 1; i <= n; i ++ ) {
		//cout << dep[i] << ' ' << sz[i] << ' ' << head[i] << '\n';
	//}
	
	for(auto [u, v] : ed) {
		cout << query(u) << '\n';
		//for(int i = 1; i <= n; i ++ ) cout << t.get(id[i]) << ' ';
		//cout << '\n';
		upd(u, a[v]);
	};
	
};

/*
6
3 6 3 9 4 5 
1 2
1 3
3 4
2 5
3 6
*/

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	
	while(tt -- ){
		solve();
	};
	
};

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