結果

問題 No.1154 シュークリームゲーム（Hard）
コンテスト
ユーザー gyh
提出日時 2025-12-31 12:30:29
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,067 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,167 ms
コンパイル使用メモリ 198,648 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-31 12:30:34
合計ジャッジ時間 3,234 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 35 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//Date: 2025-07-28 09:30:47
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define P emplace_back
#define CLEAR(a, v) memset(a, (v), sizeof(a))
#define pii pair<int, int>
#define fi first
#define se second
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
//char buf[1 << 20], *p1, *p2;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
inline int rd() {
    int s = 0, m = 0; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') m = 1; ch = getchar();}
    while(isdigit(ch)) s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
    return m ? -s : s;
}
bool MBE;
namespace SOLVER {
const int N = 1005, inf = 1e18l;
int n, x[N], b[N], rt[N], ls[N], rs[N], val[N], sz[N], cnt; vector<int> g[N];
int merge(int p, int q) {
    if(!p || !q) return p + q; if(val[p] < val[q]) swap(p, q);
    swap(ls[p], rs[p]), ls[p] = merge(ls[p], q); return p;
}
void ins(int p, int x) {val[++cnt] = x, rt[p] = merge(rt[p], cnt), sz[p]++;}
int pop(int p) {int x = val[rt[p]]; rt[p] = merge(ls[rt[p]], rs[rt[p]]), sz[p]--; return x;}
void dfs(int u, int p) {
    for(int v : g[u]) if(v != p) dfs(v, u), b[u] += b[v], rt[u] = merge(rt[u], rt[v]), sz[u] += sz[v];
    int now = x[u]; while(rt[u]) {
        if(now > val[rt[u]]) {ins(u, now), now = inf; break;}
        if(sz[u] == 1) break; now -= pop(u), now += pop(u);
    }
    if(now != inf) {if(sz[u] % 2) b[u] += now - pop(u); else ins(u, now);}
}
void MAIN() {
    n = rd(); rep(i, 1, n) x[i] = rd(); 
    rep(i, 2, n) {int u = rd(), v = rd(); g[u].P(v), g[v].P(u);}
    dfs(1, 0); ins(1, b[1]); int ans = 0, fl = 1;
    while(rt[1]) ans += fl * pop(1), fl *= -1; cout << ans << endl;
}
}
bool MED;
signed main() {
    // freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    // cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    for(int tt = 1; tt; tt--) SOLVER::MAIN();
    cerr << (&MBE - &MED) / 1024 << " KB, " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
    return 0;
}
0