結果

問題 No.2654 [Cherry 6th Tune] Re: start! (Black Sheep)
ユーザー kotatsugamekotatsugame
提出日時 2024-02-23 22:46:08
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 575 ms / 7,000 ms
コード長 2,233 bytes
コンパイル時間 1,666 ms
コンパイル使用メモリ 89,896 KB
実行使用メモリ 68,672 KB
最終ジャッジ日時 2024-02-23 22:46:23
合計ジャッジ時間 14,003 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
11,712 KB
testcase_01 AC 4 ms
11,712 KB
testcase_02 AC 4 ms
11,712 KB
testcase_03 AC 290 ms
23,872 KB
testcase_04 AC 248 ms
23,232 KB
testcase_05 AC 150 ms
18,880 KB
testcase_06 AC 38 ms
13,888 KB
testcase_07 AC 115 ms
17,728 KB
testcase_08 AC 152 ms
19,648 KB
testcase_09 AC 297 ms
24,128 KB
testcase_10 AC 36 ms
13,760 KB
testcase_11 AC 172 ms
20,672 KB
testcase_12 AC 27 ms
13,376 KB
testcase_13 AC 160 ms
20,160 KB
testcase_14 AC 358 ms
27,456 KB
testcase_15 AC 363 ms
26,688 KB
testcase_16 AC 133 ms
19,008 KB
testcase_17 AC 289 ms
24,640 KB
testcase_18 AC 96 ms
17,088 KB
testcase_19 AC 383 ms
26,944 KB
testcase_20 AC 157 ms
20,160 KB
testcase_21 AC 179 ms
20,928 KB
testcase_22 AC 174 ms
20,672 KB
testcase_23 AC 4 ms
11,712 KB
testcase_24 AC 4 ms
11,712 KB
testcase_25 AC 4 ms
11,712 KB
testcase_26 AC 4 ms
11,712 KB
testcase_27 AC 4 ms
11,712 KB
testcase_28 AC 416 ms
28,352 KB
testcase_29 AC 408 ms
28,224 KB
testcase_30 AC 418 ms
28,224 KB
testcase_31 AC 401 ms
28,352 KB
testcase_32 AC 383 ms
28,224 KB
testcase_33 AC 575 ms
68,672 KB
testcase_34 AC 239 ms
28,764 KB
testcase_35 AC 225 ms
19,008 KB
testcase_36 AC 254 ms
59,328 KB
testcase_37 AC 221 ms
19,008 KB
testcase_38 AC 254 ms
59,328 KB
testcase_39 AC 4 ms
11,712 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cassert>
using namespace std;
int N;
int A[2<<17];
vector<int>G[2<<17];
multiset<int>L,R;
long long Lsum=0,Rsum=0;
long long ans[2<<17];
map<int,int>cnt;
void dfs(int u,int p)
{
	cnt[A[u]]++;
	if(L.size()==R.size())
	{
		R.insert(A[u]);Rsum+=A[u];
		int a=*R.begin();R.erase(R.begin());Rsum-=a;
		L.insert(a);Lsum+=a;
	}
	else if(L.size()==R.size()+1)
	{
		L.insert(A[u]);Lsum+=A[u];
		auto it=L.end();it--;
		int a=*it;L.erase(it);Lsum-=a;
		R.insert(a);Rsum+=a;
	}
	else assert(false);
	assert(L.size()==R.size()||L.size()==R.size()+1);
	if(L.size()+R.size()<3)ans[u]=-1;
	else
	{
		assert(!R.empty());
		int mn=*L.begin(),mx=*R.rbegin();
		if(mn==mx)ans[u]=1;
		else
		{
			ans[u]=9e18;
			{//del min
				long long mid=*R.begin();
				long long ret=0;
				ret+=mid*(L.size()-1)-(Lsum-mn);
				ret+=Rsum-mid*R.size();
				if(mid==mn)
				{
					ret+=cnt[mid]-1;
					ret-=(L.size()+R.size())-cnt[mid];
					ans[u]=min(ans[u],ret);
				}
				else
				{
					assert(mid>mn);
					ans[u]=min(ans[u],ret);
				}
			}
			{//del max
				int mx=*R.rbegin();
				long long mid=*L.rbegin();
				long long ret=0;
				ret+=mid*L.size()-Lsum;
				ret+=(Rsum-mx)-mid*(R.size()-1);
				if(mx==mid)
				{
					ret+=cnt[mid]-1;
					ret-=(L.size()+R.size())-cnt[mid];
					ans[u]=min(ans[u],ret);
				}
				else
				{
					assert(mx>mid);
					ans[u]=min(ans[u],ret);
				}
			}
		}
	}
	for(int v:G[u])if(v!=p)dfs(v,u);
	assert(L.size()==R.size()||L.size()==R.size()+1);
	assert(!L.empty());
	cnt[A[u]]--;
	if(*L.rbegin()>=A[u])
	{
		auto it=L.find(A[u]);
		assert(it!=L.end());
		L.erase(it);
		Lsum-=A[u];
		if(L.size()<R.size())
		{
			int a=*R.begin();R.erase(R.begin());Rsum-=a;
			L.insert(a);Lsum+=a;
		}
	}
	else
	{
		auto it=R.find(A[u]);
		assert(it!=R.end());
		R.erase(it);
		Rsum-=A[u];
		if(L.size()>R.size()+1)
		{
			auto it=L.end();it--;
			int a=*it;L.erase(it);Lsum-=a;
			R.insert(a);Rsum+=a;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N;
	for(int i=0;i<=N;i++)cin>>A[i];
	for(int i=1;i<=N;i++)
	{
		int u,v;cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(0,-1);
	for(int i=1;i<=N;i++)cout<<ans[i]<<"\n";
}
0