Submission #914040

#	Time	Username	Problem	Language	Result	Execution time	Memory
914040		amirhoseinfar1385	Construction of Highway (JOI18_construction)	C++17	100 / 100	360 ms	25040 KiB

construction

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
vector<int>adj[maxn];
int all[maxn],part[maxn],parh[maxn],high[maxn],sz[maxn],n,timea=0;
pair<int,int>stf[maxn];
vector<pair<int,int>>val[maxn];
pair<int,int>alle[maxn];

bool cmp(int a,int b){
	return sz[a]>sz[b];
}

struct fen{
	int fn[maxn];
	vector<int>allv;
	void clear(){
		for(auto x:allv){
			fn[x]=0;
		}
		allv.clear();
	}
	void upd(int i,int w){
		//cout<<"wtf inf: "<<i<<" "<<w<<endl;
		i++;
		while(i<maxn){
			allv.push_back(i);
			fn[i]+=w;
			i+=((-i)&i);
		}
	}
	int pors(int i){
		//cout<<"tof pi: "<<i<<" ";
		i++;
		int ret=0;
		while(i>0){
			ret+=fn[i];
			i-=((-i)&i);
		}
		//cout<<ret<<endl;
		return ret;
	}
}fn;

void pre(int u=1,int par=1){
	if(u!=1){
		sort(adj[u].begin(),adj[u].end());
		adj[u].erase(lower_bound(adj[u].begin(),adj[u].end(),par));
	}
	part[u]=par;
	sz[u]=1;
	for(auto x:adj[u]){
		high[x]=high[u]+1;
		pre(x,u);
		sz[u]+=sz[x];
	}
	sort(adj[u].begin(),adj[u].end(),cmp);
}

void dfs(int u=1,int par=1){
	timea++;
	stf[u].first=timea;
	parh[u]=par;
	if(adj[u].size()>0){
		dfs(adj[u][0],par);
	}
	for(int i=1;i<(int)adj[u].size();i++){
		dfs(adj[u][i],adj[u][i]);
	}
	stf[u].second=timea;
}

void upd(int u,int w){
	//cout<<u<<" "<<w<<" "<<parh[u]<<endl;
	int ted=high[u]-high[parh[u]]+1;
	u=parh[u];
	int now=0;
	while((int)val[u].size()>0){
		if(val[u].back().first+now<=ted){
			now+=val[u].back().first;
			val[u].pop_back();
			continue;
		}
		val[u].back().first-=ted-now;
		break;
	}
	val[u].push_back(make_pair(ted,w));
	if(u==1){
		return ;
	}
	return upd(part[u],w);
}

int get(int u){
//	//cout<<"inget: "<<u<<endl;
	int ted=high[u]-high[parh[u]]+1;
	int now=0;
	int ph=parh[u];
	if((int)val[ph].size()==0){
		if(ph==1){
			return 0;
		}
		return get(part[parh[u]]);
	}
	u=parh[u];
	vector<pair<int,int>>tof;
	for(int i=(int)val[u].size()-1;i>=0;i--){
		if(val[u][i].first+now<=ted){
			tof.push_back(val[u][i]);
			now+=val[u][i].first;
		}
		else{
			tof.push_back(make_pair(ted-now,val[u][i].second));
			break;
		}
	}
//	//cout<<"injy: "<<u<<endl;
	reverse(tof.begin(),tof.end());
	long long ret=0;
	for(auto x:tof){
		ret+=x.first*fn.pors(x.second-1);
		fn.upd(x.second,x.first);
	}
//	//cout<<"oonjy: "<<u<<endl;
	if(u==1){
		return ret;
	}
	ret+=get(part[parh[u]]);
	return ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	cin>>n;
	vector<int>allind;
	for(int i=1;i<=n;i++){
		cin>>all[i];
		allind.push_back(all[i]);
	}	
	sort(allind.begin(),allind.end());
	allind.resize(unique(allind.begin(),allind.end())-allind.begin());
	for(int i=1;i<=n;i++){
		all[i]=lower_bound(allind.begin(),allind.end(),all[i])-allind.begin();
	}
	for(int i=0;i<n-1;i++){
		cin>>alle[i].first>>alle[i].second;
		adj[alle[i].first].push_back(alle[i].second);
		adj[alle[i].second].push_back(alle[i].first);
	}
	pre();
	dfs();
	upd(1,all[1]);
	////cout<<"sa;am"<<endl;
	for(int i=0;i<n-1;i++){
		if(high[alle[i].first]>high[alle[i].second]){
			swap(alle[i].first,alle[i].second);
		}
		cout<<get(alle[i].first)<<endl;
//		//cout<<"wtf"<<endl;
		upd(alle[i].second,all[alle[i].second]);
//		//cout<<"radshod"<<endl;
		fn.clear();
	}
}

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