Submission #335381

#	Time	Username	Problem	Language	Result	Execution time	Memory
335381		amoo_safar	Construction of Highway (JOI18_construction)	C++17	16 / 100	11 ms	1004 KiB

construction

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 5e3 + 10;
const ll Inf = 2242545357980376863LL;
const int Log = 19;

int fen[N];
void Add(int idx, int x){
	assert(idx >= 1);
	for(; idx < N; idx += idx & (-idx))
		fen[idx] += x;
}
int Get(int idx){
	assert(idx >= 1);
	assert(idx < N);
	int res = 0;
	for(; idx; idx -= idx & (-idx))
		res += fen[idx];
	return res;
}

int par[N][Log], dep[N];
int val[N], ep[N];
int C[N];

int Blift(int u, int h){
	for(int i = 0; i < Log; i++)
		if(h >> i & 1)
			u = par[u][i];
	return u;
}

typedef pair<int, int> pii;
vector<pii> A;
void Solve(int rt, int u, int v){
	// cerr << "! " << rt << ' ' << u << ' ' << v << '\n';
	if(rt == v) return ;
	if(ep[rt] == u){
		A.pb({val[rt], dep[v] - dep[rt]});
		return ;
	}
	int v1 = v;
	int v2 = ep[rt];
	if(dep[v1] > dep[v2])
		v1 = Blift(v1, dep[v1] - dep[v2]);
	else
		v2 = Blift(v2, dep[v2] - dep[v1]);
	// assert(v1 != v2);
	for(int l = Log - 1; l >= 0; l--){
		if(par[v1][l] != par[v2][l])
			v1 = par[v1][l], v2 = par[v2][l];
	}
	A.pb({val[rt], dep[v2] - dep[rt]});
	ep[v2] = ep[rt];
	val[v2] = val[rt];
	Solve(v1, u, v);
	return ;
}
ll Calc(){
	reverse(all(A));
	ll res = 0;
	for(auto X : A){
		res += 1ll * X.S * Get(X.F - 1);
		Add(X.F, X.S);
	}
	for(auto X : A)
		Add(X.F, -X.S);
	return res;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	vector<int> V;
	for(int i = 1; i <= n; i++){
		cin >> C[i];
		V.pb(C[i]);
	}
	sort(all(V));
	for(int i = 1; i <= n; i++){
		C[i] = lower_bound(all(V), C[i]) - V.begin();
		C[i] += 3;
	}
	dep[1] = 0;
	val[1] = C[1];
	ep[1] = 1;

	int u, v;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		par[v][0] = u;
		dep[v] = dep[u] + 1;
		for(int i = 1; i < Log; i++)
			par[v][i] = par[par[v][i - 1]][i - 1];	
	
		A.clear();
		Solve(1, u, v);
		val[1] = C[v];
		ep[1] = v;
		cout << Calc() << '\n';
	}
	return 0;
}

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