Submission #604566

#	Time	Username	Problem	Language	Result	Execution time	Memory
604566		amunduzbaev	Construction of Highway (JOI18_construction)	C++17	100 / 100	918 ms	36540 KiB

construction

#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef int64_t ll;
#define int ll
#define her cout<<"here"<<endl;

const int N = 1e5 + 5;
vector<int> edges[N];
int a[N], v[N], par[N][20];
int tin[N], tout[N], t, d[N];

void dfs(int u){
	tin[u] = ++t;
	for(int j=1;j<20;j++){
		par[u][j] = par[par[u][j-1]][j-1];
	}
	for(auto x : edges[u]){
		if(x == par[u][0]) continue;
		d[x] = d[u] + 1;
		par[x][0] = u;
		dfs(x);
	}
	
	tout[u] = t;
}

bool is(int a, int b){
	return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int lca(int a, int b){
	assert(!is(a, b) && !is(b, a));
	for(int j=19;~j;j--){
		if(!is(par[a][j], b)) a = par[a][j];
	}
	
	return a;
}

struct BIT{
	int tree[N];
	void add(int i, int v){
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	int get(int i){
		int r = 0;
		for(;i>0;i-=(i&-i)) r += tree[i];
		return r;
	}
	
	int get(int l, int r){
		return get(r) - get(--l);
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	vector<int> p(n); iota(p.begin(), p.end(), 1);
	sort(p.begin(), p.end(), [&](int i, int j){
		return (a[i] < a[j]);
	});
	for(int i=0,last=0,j=0;i<n;){
		while(j<n && a[p[j]] == a[p[i]]) j++;
		last++;
		while(i < j) a[p[i]] = last, i++;
	}
	vector<ar<int, 2>> e;
	for(int i=1;i<n;i++){
		int a, b; cin >> a >> b;
		e.push_back({a, b});
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	
	par[1][0] = 1;
	dfs(1);
	v[1] = 1;
	
	for(auto [a, b] : e){
		int c = 1;
		vector<ar<int, 2>> t;
		while(!is(v[c], b) && c != b){
			//~ cout<<c<<" "<<v[c]<<" "<<b<<endl;
			int u = lca(b, v[c]);
			int x = lca(v[c], b);
			v[x] = v[c];
			t.push_back({d[u] - d[c], ::a[v[c]]});
			c = u;
		}
		//~ assert(v[c] == a);
		if(c != b) t.push_back({d[b] - d[c], ::a[v[c]]});
		v[1] = b;
		int res = 0;
		//~ for(auto x : t) cout<<x[0]<<" ";
		//~ cout<<"\n";
		//~ for(auto x : t) cout<<x[1]<<" ";
		//~ cout<<"\n";
		for(auto x : t){
			tree.add(x[1], x[0]);
			res += tree.get(x[1] + 1, N) * x[0];
		}
		
		cout<<res<<"\n";
		for(auto x : t){
			tree.add(x[1], -x[0]);
		}
		
	}
}

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