82 C General Mobilization

問題

n都市からなる国があり、都市はn-1本の双方向に通行可能な道路によって結ばれている。
都市は1,2,3,...,nとして、首都が1である。

首都に向かう方向に、各都市に毎日c[i]本の電車が走っている。
全ての都市から首都に対して、以下のようにして軍隊を招集したい。

• それぞれの軍隊の優先度が与えられる。
• はじめは各都市に一つずつ軍隊がいる。
• ある都市に二つ以上の軍隊が居た場合、優先度の最も高い軍隊が電車を使う。

このとき、それぞれの軍隊が首都に到着するのは何日目か求めよ。

制約条件

n≦5000
優先度≦10^9

方針

priority queueを都市ごとに作って（合計5000個）
愚直にシミュレーション。なんか計算量が若干あやしそうだけど通る。

ソースコード

int n,p[5000],cap[5000],a[5000],ans[5000];
vector<vector<pi> > e;

void rec(int c,int pa,int cp=0){
	if(c!=0){
		p[c]=pa; cap[c]=cp;
	}
	rep(i,e[c].size())if(e[c][i].first!=pa)
	rec(e[c][i].first,c,e[c][i].second);
}

int cnt,day;
void recur(vector<priority_queue<pi> > &qs,int c){
	int k=0;
	if(c&&p[c]==0)
		while(!qs[c].empty()&&k++<cap[c])ans[qs[c].top().second]=day, qs[c].pop(), cnt++;
	else if(c)
		while(!qs[c].empty()&&k++<cap[c])qs[p[c]].push(qs[c].top()), qs[c].pop();
	rep(i,e[c].size())if(e[c][i].first!=p[c])recur(qs,e[c][i].first);
}
void run(){
	cin>>n;
	rep(i,n)cin>>a[i];
	e.clear(); e.resize(n);
	rep(i,n-1){
		int a,b,c; cin>>a>>b>>c; a--; b--;
		e[a].pb(mp(b,c)); e[b].pb(mp(a,c));
	}
	
	rec(0,0);
	vector<priority_queue<pi> > qs(n);
	for(int i=1;i<n;i++)qs[i].push(mp(-a[i],i));
	
	cnt=1; day=0;
	while(cnt<n){
		day++;
		recur(qs,0);
	}
	rep(i,n)cout<<ans[i]<<(i==n-1?"\n":" ");
}