QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#121952 | #6514. Is it well known in Poland? | Sorting# | WA | 3ms | 10600kb | C++ | 1.3kb | 2023-07-09 01:30:33 | 2023-07-09 01:30:36 |
Judging History
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'