Submission #511267

#	Time	Username	Problem	Language	Result	Execution time	Memory
511267		fatemetmhr	Construction of Highway (JOI18_construction)	C++17	100 / 100	406 ms	48396 KiB

construction

//  ~Be name khoda~  //

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  1e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;

int ind = 1;
set <pair<int, int>> av[maxn5];
vector <int> have, liv, req, adj[maxn5];
ll fen[maxn5];
int sz[maxn5], big[maxn5], h[maxn5];
int par[maxn5], f[maxn5], fid[maxn5];
int fir[maxn5], a[maxn5];

inline void add(int id, ll val){
	for(; id < maxn5; id += id & -id){
		fen[id] += val;
		have.pb(id);
	}
	return;
}
inline ll get(int id){
	ll ret = 0;
	for(; id; id -= id & -id)
		ret += fen[id];
	return ret;
}


inline void dfs_det(int v){
	sz[v] = 1;
	big[v] = -1;
	for(auto u : adj[v]){
		h[u] = h[v] + 1;
		dfs_det(u);
		sz[v] += sz[u];
		par[u] = v;
		if(big[v] == -1 || sz[big[v]] <= sz[u])
			big[v] = u;
	}
	return;
}

inline void dfs_hld(int v, int last, int id){
	f[v] = last;
	fid[v] = id;
	//cout << v << ' ' << f[v] << ' ' << fid[v] << endl;
	if(last == v)
		fir[id] = -h[v] + 1;
	av[id].insert({-h[v], maxn5 - 5});
	//cout << "then why ? " << v << ' ' << av[id].size() << endl;
	if(big[v] != -1){
		dfs_hld(big[v], last, id);
	}
	for(auto u : adj[v]) if(u != big[v]){
		dfs_hld(u, u, ind++);
	}
	return;
}

inline ll solve(int v, int val){
	if(v == -1) return 0;
	//cout << "aha " << v << ' ' << val << endl;
	int id = fid[v];
	auto it = av[id].lower_bound(mp(-h[v], -1));
	auto itt = it;
	itt--;
	ll ret = 0;
	if(h[v] > (it->fi) * -1){
		int len = (it == av[id].end() ? fir[id] : (it->fi)) + h[v];
		if((itt->se) > 1)
			ret += get((itt->se) - 1) * len;
		add(itt->se, len);
		//cout << "begor " << ' ' << (itt->fi) << ' ' << (itt->se) << ' ' << len << ' ' << ret << endl;
	}
	
	for(; it != av[id].end();){
		itt = it;
		int len = 0;
		itt++;
		if(itt != av[id].end())
			len = (itt->fi) - (it->fi);
		else
			len = fir[id] - (it->fi);
		itt--;
		if((it -> se) > 1)
			ret += get((it->se) - 1) * len;
		add(it->se, len);
		//cout << "Look " << (it->fi) << ' ' << (it->se) << ' ' << len << ' ' << ret << ' ' << fir[id] << endl;
		it++;
		av[id].erase(itt);
	}
	
	av[id].insert({-h[v], val});
	ret += solve(par[f[v]], val);
	return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int n; cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		liv.pb(a[i]);
	}
	
	sort(all(liv));
	liv.resize(unique(all(liv)) - liv.begin());
	for(int i = 0; i < n; i++)
		a[i] = (lower_bound(all(liv), a[i]) - liv.begin()) + 1;
	
	for(int i = 0; i < n - 1; i++){
		int a, b; cin >> a >> b;
		a--; b--;
		adj[a].pb(b);
		req.pb(b);
	}
	
	par[0] = -1;
	dfs_det(0);
	dfs_hld(0, 0, 0);

	
	for(auto u : req){
		have.clear();
		ll ans = solve(u, a[u]);
		cout << ans << '\n';
		for(auto v : have)
			fen[v] = 0;
	}
	
}

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