Submission #234956

#	Time	Username	Problem	Language	Result	Execution time	Memory
234956		oolimry	Construction of Highway (JOI18_construction)	C++14	16 / 100	582 ms	23368 KiB

construction

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<long long, long long> ii;

int n;
int cnt = 0;
int arr[100005];
int low[100005];
int high[100005];
int p[100005][20];
vector<int> adj[100005];
vector<ii> edges;

///segment tree
ii tree[200005]; 
int timer = 1;
void update(int i, int v){
	for(i += n;i > 0;i >>= 1) tree[i] = ii(timer, v);
	timer++;
}

ii query(int u){
	int l = low[u], r = high[u];
	ii res = ii(0,0);
	for(l += n, r += n+1;l < r;l >>= 1, r >>= 1){
		if(l&1) res = max(res, tree[l++]);
		if(r&1) res = max(res, tree[--r]);
	}
	return res;
}
///segment tree

///segment tree 2
int tree2[100005];

void update2(int i, int v){
	for(i += n;i > 0;i >>= 1) tree2[i] += v;
}

long long query2(int l, int r){
	long long res = 0;
	for(l += n, r += n;l < r;l >>= 1, r >>= 1){
		if(l&1) res += tree2[l++];
		if(r&1) res += tree2[--r];
	}
	return res;
}

///segment tree 2

void dfs(int u, int P){
	low[u] = cnt; cnt++;
	high[u] = low[u];
	for(int v : adj[u]){
		if(v == P) continue;
		dfs(v, u);
		p[v][0] = u;
		high[u] = max(high[u], high[v]);
	}
	update(low[u], arr[u]);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n;
	vector<int> discrodile;
	for(int i = 1;i <= n;i++){
		cin >> arr[i];
		discrodile.push_back(arr[i]);
	}
	
	sort(discrodile.begin(), discrodile.end());
	discrodile.erase(unique(all(discrodile)), discrodile.end());
	
	for(int i = 1;i <= n;i++){
		arr[i] = lower_bound(all(discrodile), arr[i]) - discrodile.begin();
	}
	
	for(int i = 1;i < n;i++){
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		edges.push_back(ii(u,v));
	}
	
	dfs(1,0);
	
	for(int d = 1;d <= 19;d++){
		for(int i = 1;i <= n;i++){
			p[i][d] = p[p[i][d-1]][d-1];
			//cout << p[i][d] << " ";
		}
		//cout << "\n";
	}
	
	
	
	for(ii e : edges){
		int u = e.first, v = e.second; ///extend tree from u to v;
		//cout << "\n" << u << " " << v << ":\n";
		
		vector<ii> parts;
		while(true){
			ii root = query(u);
			
			
			int sz = 1;
			for(int d = 19;d >= 0;d--){
				int nu = p[u][d];
				if(nu == 0) continue;
				if(query(nu) != root) continue;
				u = nu;
				sz += (1 << d);
			}
			
			//cout << root.first << " " << root.second << " " << sz << "\n";
			parts.push_back(ii(root.second, sz));
			if(u == 1) break;
			u = p[u][0];
		}
		
		long long ans = 0;
		for(ii x : parts){
			ans += x.second * query2(0, x.first);
			update2(x.first, x.second);
		}
		for(ii x : parts) update2(x.first, -x.second); ///undo
		
		cout << ans << "\n";
		
		update(low[v], arr[v]);
	}
}

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