Submission #769261

#	Time	Username	Problem	Language	Result	Execution time	Memory
769261		Mohammad_Parsa	Construction of Highway (JOI18_construction)	C++17	100 / 100	928 ms	24148 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
#define lc (2*id)
#define rc (2*id+1)
#define md ((s+e)/2)
#define ln (e-s+1)

typedef long long ll;

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

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;
}
void upds(int k,int x,int id=1,int s=1,int e=n){
	if(ln==1){
		seg[id]=x;
		return;
	}
	if(k<=md) upds(k,x,lc,s,md);
	else upds(k,x,rc,md+1,e);
	seg[id]=max(seg[lc],seg[rc]);
}

int gets(int l,int r,int id=1,int s=1,int e=n){
	if(l>e || s>r){
		return 0;
	}
	if(s>=l && e<=r){
		return seg[id];
	}
	return max(gets(l,r,lc,s,md),gets(l,r,rc,md+1,e));
}
		

int lca(int u,int 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];
		}
	}
	return u;
}

void dfs(int v=1){
	st[v]=++T;
	for(auto u:vec[v]){
		dfs(u);
	}
	fn[v]=T;
}

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];
		vec[a[i]].pb(b[i]);
	}
	dfs();
	for(int j=1;j<lg;j++){
		for(int i=1;i<=n;i++){
			sp[i][j]=sp[sp[i][j-1]][j-1];
		}
	}
	upds(1,1);
	b[-1]=1;
	for(int i=0;i<n-1;i++){
		int u=1;	
		vc.clear();	
		while(u!=b[i]){
			int v;
			int x=b[gets(st[u],fn[u])-2];
			//cout<<u<<endl;
			if(u==a[i])v=b[i];
			else v=lca(a[i],x);
			ll t=h[v]-h[u];
			ans[i]+=t*(get(N-1)-get(c[x]));
			upd(c[x],t);
			vc.pb(mk(c[x],t));
			u=v;
		}
		for(auto [p,q]:vc){
			upd(p,-q);
		}
		upds(st[b[i]],i+2);
		cout<<ans[i]<<endl;
	}
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:112:6: warning: array subscript -1 is below array bounds of 'int [100007]' [-Warray-bounds]
  112 |  b[-1]=1;
      |  ~~~~^
construction.cpp:18:17: note: while referencing 'b'
   18 | int n,c[N],a[N],b[N],h[N],p[N],fen[N],sp[N][lg],x;
      |                 ^

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