QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#147392 | #6514. Is it well known in Poland? | BUET_POTATOES | WA | 2ms | 6668kb | C++20 | 2.6kb | 2023-08-23 03:39:56 | 2023-08-25 01:25:25 |
Judging History
answer
#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt")
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
#define DBG(a) cerr<< "line "<<__LINE__ <<" : "<< #a <<" --> "<<(a)<<endl
#define eps 1e-8
//#define eq(x,y) (fabs((x)-(y)) < eps)
using namespace std;
typedef long long ll;
typedef long long LL;
typedef long double Tf;
typedef pair<ll,ll>pii;
const ll mod = 998244353;
//const ll mod = 1e9+7;
//long double pi = acosl(-1);
const ll infl = 1e18+100;
const int inf = 1e9+100;
const int nmax = 1e5+50;
//const int MAXLG = log2(nmax)+1;
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
//typedef tree< ll, nullptr_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ost;
priority_queue<ll>pq[nmax];
void solve(int ces){
int n;
cin>>n;
vector< vector<int> >g(n+1);
vector<int>A(n+1);
for(int i=1; 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);
}
ll tmpans = 0;
auto dfs = [&](auto &dfs, int u, int p) -> void {
// cout<<"dfs at "<<u<<endl;
for(int v : g[u]) if(v!=p){
dfs(dfs, v, u);
if(pq[u].size() < pq[v].size())
swap(pq[u], pq[v]);
while(!pq[v].empty()){
pq[u].push(pq[v].top());
pq[v].pop();
}
}
ll cur = A[u];
while(pq[u].size() >= 2){
if(cur >= pq[u].top()){
pq[u].push(cur);
return;
}
cur -= pq[u].top();
pq[u].pop();
cur += pq[u].top();
pq[u].pop();
}
if(!pq[u].empty()){
if(pq[u].top() > cur){
cur -= pq[u].top();
pq[u].pop();
tmpans += cur;
}
else pq[u].push(cur);
}
else pq[u].push(cur);
};
dfs(dfs, 1, 0);
ll wholsum = accumulate(A.begin(), A.end(), 0LL);
while(!pq[1].empty()){
wholsum += pq[1].top();
pq[1].pop();
if(pq[1].empty()) wholsum -= tmpans;
if(!pq[1].empty()){
wholsum -= pq[1].top();
pq[1].pop();
if(pq[1].empty()) wholsum += tmpans;
}
}
cout<<wholsum/2<<"\n";
}
/*
*/
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int tc=1;
// cin>>tc;
for(int ces=1; ces<=tc; ces++){
solve(ces);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 6668kb
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: 2ms
memory: 6664kb
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:
5121426650
result:
wrong answer 1st numbers differ - expected: '4611098449', found: '5121426650'