Submission #506126

#	Time	Username	Problem	Language	Result	Execution time	Memory
506126		Koosha_mv	Construction of Highway (JOI18_construction)	C++14	100 / 100	485 ms	21560 KiB

construction

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=1e5+99;

int n,t,col[N],sz[N],up[N],X[N],Y[N],h[N],par[N];
ll fenwik[N];
vector<int> g[N];
vector<pair<int,int> > res,v[N];

void add(int x, int val){ for(x++;x<N;x+=x&-x) fenwik[x]+=val; }
ll get(int x) { ll res=0; for (x++;x>0;x-=x&-x) res+=fenwik[x]; return res; }

void dfs1(int u){
	int x=-1;
	sz[u]=1;
	f(i,0,g[u].size()){
		int v=g[u][i];
		dfs1(v);
		sz[u]+=sz[v];
		if(x==-1 || sz[v]>sz[g[u][x]]){
			x=i;
		}
	}
	if(x!=-1){
		swap(g[u][0],g[u][x]);
	}
}
void dfs2(int u){
	//cout<<u<<" : "<<up[u]<<endl;
	int t=1;
	for(auto v : g[u]){
		h[v]=h[u]+1;
		if(t){
			up[v]=up[u];
		}
		else{
			up[v]=v;
		}
		dfs2(v);
		t=0;
	}
	v[up[u]].pb({col[u],1});
}
void del(int u,int x,int c){
	vector<pair<int,int> > vec;
	int t=x;
	while(t>0){
		int p=min(t,v[u].back().S);
		//cout<<u<<" : "<<v[u].back().F<<" "<<v[u].back().S<<endl;
		v[u].back().S-=p;
		t-=p;
		vec.pb({v[u].back().F,p});
		//erorp(vec.back());
		if(v[u].back().S>0 || t==0) break;
		v[u].pop_back();
	}
	v[u].pb({c,x});
	reverse(all(vec));
	for(auto p : vec){
		res.pb(p);
	}
	//eror(res.size());
}
void query(int u,int c){
	while(u>0){
		del(up[u],h[u]-h[up[u]]+1,c);
		u=par[up[u]];
	}
}
void get_ans(){
	//fill(fenwik,fenwik+N,0);
	ll ans=0;
	//cout<<"RES : "<<endl;
	res[0].S--;
	for(auto p : res){
		//erorp(p);
		add(p.F,p.S);
		ans+=get(p.F-1)*p.S;
	}
	for(auto p : res){
		add(p.F,-p.S);
	}
	res.clear();
	cout<<ans<<endl;
}

int main(){
	vector<int> vec;
	cin>>n;
	f(i,1,n+1){
		cin>>col[i];
		vec.pb(col[i]);
	}
	sort(all(vec));
	f(i,1,n+1){
		col[i]=lower_bound(all(vec),col[i])-vec.begin()+1;
	}
	f(i,1,n){
		cin>>X[i]>>Y[i];
		par[Y[i]]=X[i];
		g[X[i]].pb(Y[i]);
	}
	up[1]=1;
	dfs1(1);
	dfs2(1);
	f(i,1,n){
		query(Y[i],col[Y[i]]);
		get_ans();
		//if(i==2) return 0;
	}
}

Compilation message (stderr)

construction.cpp: In function 'void dfs1(int)':
construction.cpp:8:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   35 |  f(i,0,g[u].size()){
      |    ~~~~~~~~~~~~~~~             
construction.cpp:35:2: note: in expansion of macro 'f'
   35 |  f(i,0,g[u].size()){
      |  ^

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