QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#147392#6514. Is it well known in Poland?BUET_POTATOESWA 2ms6668kbC++202.6kb2023-08-23 03:39:562023-08-25 01:25:25

Judging History

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

  • [2023-08-25 01:25:25]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:6668kb
  • [2023-08-23 03:39:56]
  • 提交

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'