QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#121960 | #6514. Is it well known in Poland? | Sorting# | WA | 3ms | 11244kb | C++ | 1.4kb | 2023-07-09 01:43:20 | 2023-07-09 01:43:34 |
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<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'