QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#121960#6514. Is it well known in Poland?Sorting#WA 3ms11244kbC++1.4kb2023-07-09 01:43:202023-07-09 01:43:34

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-09 01:43:34]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:11244kb
  • [2023-07-09 01:43:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=1e5+1;
int n;
ll a[N];
ll s=0;
vector<int>adj[N];
set<ll>luv[N];
ll ans=0;
vector<ll>die;
void dfs(int id,int p){
	int bc=0;
	for(auto c:adj[id]){
		if(c==p) continue;
		dfs(c,id);
		if(luv[c].size()>luv[bc].size()) bc=c;
	}
	if(bc!=0){
		for(auto c:adj[id]){
			if(c==p || c==bc) continue;
			for(auto d:luv[c]) luv[bc].insert(d);
			luv[c].clear();
		}
		swap(luv[bc],luv[id]);
	}
	//for(auto c:luv[id]) cout << id << ": " << c << ";"; 
	while(!luv[id].empty() && *luv[id].rbegin()>=a[id]){
		if(luv[id].size()==1){
			ll evil=*luv[id].rbegin()-a[id];
			if(n%2==1) ans+=evil;
			else ans-=evil;
			luv[id].clear();
			return;
		}
		else{
			a[id]-=*luv[id].rbegin();
			auto it=luv[id].end();--it;luv[id].erase(it);
			a[id]+=*luv[id].rbegin();
			it=luv[id].end();--it;luv[id].erase(it);
		}
	}
	//cout << "haah " << a[id] << endl;
	luv[id].insert(a[id]);
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n;
	for(int i=1; i<=n ;i++){
		cin >> a[i];
		s+=a[i];
	}
	for(int i=1; i<n ;i++){
		int u,v;cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1,0);
	int sgn=1;
	while(!luv[1].empty()){
		ans+=*luv[1].rbegin()*sgn;
		sgn*=-1;
		auto it=luv[1].end();--it;luv[1].erase(it);
	}
	cout << (ans+s)/2 << '\n';
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 10600kb

input:

5
1 5 3 2 4
1 2
1 3
2 4
2 5

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 1ms
memory: 10576kb

input:

20
530933472 920863930 136179483 46535289 291417568 338674057 731327836 375973098 986104110 203163644 489326483 785212564 712578139 801609721 666347686 282530991 823910542 217884304 785578553 116701831
8 3
18 19
11 20
2 18
8 13
5 15
12 16
7 8
10 9
13 6
17 10
17 18
13 15
18 4
13 12
1 14
17 15
15 14
5...

output:

4611098449

result:

ok 1 number(s): "4611098449"

Test #3:

score: 0
Accepted
time: 1ms
memory: 11244kb

input:

20
384529189 217795442 901954855 742992564 354875060 497288585 40376145 575315239 263212445 574630916 520470316 917128880 461333242 407666839 565926566 390970156 568486150 291329847 493439854 637783217
10 17
19 8
20 17
7 17
9 6
17 14
16 18
4 3
9 14
6 2
14 18
13 4
11 15
9 3
7 12
16 1
8 14
5 14
9 15

output:

4410782058

result:

ok 1 number(s): "4410782058"

Test #4:

score: 0
Accepted
time: 3ms
memory: 10600kb

input:

19
601996737 696498327 385657564 527861058 529330573 376647612 223077352 338754937 682264670 671903443 645156487 755321105 978945836 120368247 611275923 947566064 98892994 858404931 401419272
11 14
8 14
3 6
13 12
16 15
1 4
11 4
2 7
4 3
15 5
2 1
13 5
10 16
9 16
1 17
18 6
3 19
5 7

output:

5848746543

result:

ok 1 number(s): "5848746543"

Test #5:

score: -100
Wrong Answer
time: 3ms
memory: 10856kb

input:

1000
379354617 199235046 102686848 841958378 178689385 896777301 798019293 538540178 877449071 825184825 426375184 882476194 614078703 438824267 731949932 770345838 655572525 687098129 758287148 690715403 984914877 365231609 752380073 509777049 511312331 889780846 745450511 740863321 552773286 15071...

output:

252918082620

result:

wrong answer 1st numbers differ - expected: '252915929540', found: '252918082620'