Submission #769253

#	Time	Username	Problem	Language	Result	Execution time	Memory
769253		Mohammad_Parsa	Construction of Highway (JOI18_construction)	C++17	0 / 100	1 ms	340 KiB

construction

/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;

//#define endl '\n'
#define pb push_back
#define F first
#define S second
#define mk make_pair
typedef long long ll;

const int N=1e5+7,lg=20;
int n,c[N],a[N],b[N],h[N],p[N],x[N],fen[N],sp[N][lg];
pair<int,int>com[N];
ll ans[N];
vector<pair<int,int>>vec;

void upd(int i,int x){
	for(;i<N;i+=i&(-i)){
		fen[i]+=x;
	}
}

int get(int i){
	int ans=0;
	for(;i;i-=i&(-i)){
		ans+=fen[i];
	}
	return ans;
}

int lca(int u,int v){
	int f=v;
	for(int i=lg-1;i>=0;i--){
		if(h[sp[u][i]]>=h[v]){
			u=sp[u][i];
		}
		if(h[sp[v][i]]>=h[u]){
			v=sp[v][i];
		}
	}
	for(int i=lg-1;i>=0;i--){
		if(sp[u][i]!=sp[v][i]){
			u=sp[u][i];
			v=sp[v][i];
		}
	}
	x[v]=f;
	return u;
}


int main(){
	ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i];
		com[i]=mk(c[i],i);
	}
	int k=1;
	sort(com,com+n+1);
	for(int i=1;i<=n;i++){
		c[com[i].S]=k;
		if(com[i].F!=com[i+1].F)k++;
	}
	for(int i=0;i<n-1;i++){
		cin>>a[i]>>b[i];
		p[b[i]]=a[i];
		h[b[i]]=h[a[i]]+1;
		sp[b[i]][0]=a[i];
	}
	for(int j=1;j<lg;j++){
		for(int i=1;i<=n;i++){
			sp[i][j]=sp[sp[i][j-1]][j-1];
		}
	}
	x[1]=1;
	for(int i=0;i<n-1;i++){
		int u=1;	
		vec.clear();	
		while(u!=b[i]){
			int v;
			if(u==a[i])v=b[i];
			else v=lca(a[i],x[u]);
			//cout<<u<<" "<<v<<endl;
			ll t=h[v]-h[u];
			//cout<<get(N-1)-get(c[x[u]])<<endl;
			ans[i]+=t*(get(N-1)-get(c[x[u]]));
			upd(c[x[u]],t);
			vec.pb(mk(u,t));
		//	x[u]=b[i];
			u=v;
		}
		for(auto [p,q]:vec){
			upd(c[x[p]],-q);
			x[p]=b[i];
		}
		x[1]=b[i];
		x[b[i]]=b[i];
		cout<<ans[i]<<endl;
	}
}

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