Submission #626681

#	Time	Username	Problem	Language	Result	Execution time	Memory
626681		codr0	Construction of Highway (JOI18_construction)	C++14	100 / 100	1014 ms	23500 KiB

construction

// Code by Parsa Eslami

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>

#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)x.size())
#define bit(i,j) ((j>>i)&1)
#define pb push_back
#define lc 2*id
#define rc 2*id+1
#define dmid int mid=(r+l)/2
#define err(x) cerr<#x<<" : "<<x<<'\n'
#define F first
#define S second

using namespace std;
const int N=1e5+4;
const int lg=20;
vector<int> adj[N];
int val[N];
int h[N],par[lg][N],st[N],en[N],tme;
int ver[N];
int seg[4*N];
int n;
struct fenwick{
	int fen[N];
	void add(int k,int x){
		while(k>0){
			fen[k]+=x;
			k-=(k&(-k));
		}
	}
	int get(int k){
		int rt=0;
		while(k<N){
			rt+=fen[k];
			k+=(k&(-k));
		}
		return rt;
	}
};
fenwick fen;

	int Get(){
		int x; cin>>x; return x;
	}	

	int PAR(int v,int k){
		while(k>0){
			v=par[__builtin_ctz(k)][v];
			k-=(k&(-k));
		}
		return v;
	}

	int LCA(int u,int v){
		if(h[u]<h[v]) swap(u,v);
		u=PAR(u,h[u]-h[v]);
		if(u==v) return u;
		FORR(j,lg-1,0) if(par[j][u]!=par[j][v]){
			u=par[j][u];
			v=par[j][v];
		}
		return par[0][v];
	}

	void upd(int id,int l,int r,int ind,int x){
		if(ind<l||ind>=r) return;
		seg[id]=x;
		if(l+1==r) return;
		dmid;
		upd(lc,l,mid,ind,x);
		upd(rc,mid,r,ind,x);
	}

	int get(int id,int l,int r,int s,int e){
		if(s>=r||e<=l) return 0;
		if(s<=l&&e>=r) return seg[id];
		dmid;
		return max(get(lc,l,mid,s,e),get(rc,mid,r,s,e));
	}

	ll GET(int u){
		vector<pii> vc;
		int root=1;
		while(1){	
			int w=ver[get(1,1,n+1,st[root],en[root]+1)];
			int y=val[w];
			w=LCA(u,w);
			vc.pb({y,h[w]-h[root]+1});
			if(w==u) break;
			root=PAR(u,h[u]-h[w]-1);
		}
		//for(pii x:vc) cout<<x.F<<"."<<x.S<<" ";
		//cout<<'\n';
		ll rt=0;
		for(pii x:vc){
			rt+=fen.get(x.F+1)*x.S;
			fen.add(x.F,x.S);
		}
		for(pii x:vc) fen.add(x.F,-x.S);
		return rt;
	}

	void dfs(int v){
		st[v]=++tme;
		for(int u:adj[v]) dfs(u);
		en[v]=tme;
	}

	int32_t main(){
	iostream::sync_with_stdio(0); cin.tie(0);

	n=Get();
	FOR(i,1,n) val[i]=Get();
	vector<pii> vc;
	FOR(i,1,n) vc.pb({val[i],i});
	sort(all(vc)); int x0=0;
	FOR(i,0,SZ(vc)-1){
		if(i==0||vc[i].F!=vc[i-1].F) x0++;
		val[vc[i].S]=x0;
	}
	int U[n],V[n];
	FOR(i,1,n-1){
		U[i]=Get(); V[i]=Get();
		int u=U[i],v=V[i];
		adj[u].pb(v);
		par[0][v]=u;
		h[v]=h[u]+1;
	}
	FOR(j,1,lg-1) FOR(i,1,n) par[j][i]=par[j-1][par[j-1][i]];
	dfs(1);
	upd(1,1,n+1,st[1],1); ver[1]=1;
	FOR(i,1,n-1){
		cout<<GET(U[i])<<'\n';
		upd(1,1,n+1,st[V[i]],i+1); ver[i+1]=V[i];
	}

	return 0;
	}

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