QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#121952#6514. Is it well known in Poland?Sorting#WA 3ms10600kbC++1.3kb2023-07-09 01:30:332023-07-09 01:30:36

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:30:36]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:10600kb
  • [2023-07-09 01:30:33]
  • 提交

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<int>luv[N];
ll ans=0;
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(c);
			luv[c].clear();
		}
		swap(luv[bc],luv[id]);
	}
	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);
		}
	}
	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: 1ms
memory: 10456kb

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: -100
Wrong Answer
time: 3ms
memory: 10600kb

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:

4407552756

result:

wrong answer 1st numbers differ - expected: '4611098449', found: '4407552756'