Submission #1280050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280050		PlayVoltz	Construction of Highway (JOI18_construction)	C++20	100 / 100	276 ms	85996 KiB

construction

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
using namespace std;
 
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n;
vector<int> vect, depth, par, sz, head, ft;
vector<vector<int> > graph;

void dfs(int node, int p, int d){
	depth[node]=d;
	par[node]=p;
	if (graph[node].size()>1&&graph[node][0]==p)swap(graph[node][0], graph[node][1]);
	for (auto &num:graph[node])if (num!=p){
		dfs(num, node, d+1);
		sz[node]+=sz[num];
		if (sz[num]>sz[graph[node][0]])swap(num, graph[node][0]);
	}
}

void hld(int node, int p){
	for (auto num:graph[node])if (num!=p){
		if (num==graph[node][0])head[num]=head[node];
		else head[num]=num;
		hld(num, node);
	}
}

int query(int i){
	int res=0;
	for (;i;i-=i&-i)res+=ft[i];
	return res;
}

void up(int i, int v){
	for (;i<ft.size();i+=i&-i)ft[i]+=v;
}

int calc(vector<pii> vect){
	vector<int> ord;
	for (auto a:vect)ord.pb(a.fi);
	sort(ord.begin(), ord.end());
	ord.erase(unique(ord.begin(), ord.end()), ord.end());
	for (int i=0; i<vect.size(); ++i)vect[i].fi=lower_bound(ord.begin(), ord.end(), vect[i].fi)-ord.begin()+1;
	ft.clear();
	ft.resize(ord.size()+1, 0);
	int res=0;
	for (auto c:vect){
		res+=(query(ord.size())-query(c.fi))*c.se;
		up(c.fi, c.se);
	}
	return res;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	vect.resize(n+1);
	graph.resize(n+1);
	sz.resize(n+1, 1);
	par.resize(n+1, 0);
	head.resize(n+1, 0);
	depth.resize(n+1);
	for (int i=1; i<=n; ++i)cin>>vect[i];
	vector<int> ord;
	for (int i=1, a, b; i<n; ++i){
		cin>>a>>b;
		ord.pb(b);
		graph[a].pb(b);
		graph[b].pb(a);
	}
	dfs(1, 0, 1);
	head[1]=1;
	hld(1, 0);
	vector<stack<pii> > st(n+1);
	for (auto c:ord){
		int cc=vect[c];
		vector<pii> res;
		while (c){
			int d=depth[c]-depth[head[c]]+1, t=0;
			c=head[c];
			vector<pii> temp;
			while (st[c].size()&&st[c].top().se<=d){
				temp.pb(mp(st[c].top().fi, st[c].top().se-t));
				t=st[c].top().se;
				st[c].pop();
			}
			if (st[c].size())temp.pb(mp(st[c].top().fi, d-t));
			st[c].push(mp(cc, d));
			reverse(temp.begin(), temp.end());
			for (auto a:temp)res.pb(a);
			c=par[c];
		}
		reverse(res.begin(), res.end());
		cout<<calc(res)<<"\n";
	}
}

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