結果

問題 No.1154 シュークリームゲーム（Hard）
ユーザー Caiiiiiiii
提出日時 2025-07-12 17:25:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,317 bytes
コンパイル時間 1,923 ms
コンパイル使用メモリ 194,204 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-07-12 17:25:54
合計ジャッジ時間 7,746 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 RE * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:53:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
main.cpp:55:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   55 |     scanf("%d", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~
main.cpp:57:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   57 |     scanf("%d%d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

using LL = long long;

const int N = 1e3 + 7;

int n, m, a[N];
std::vector<int> e[N];
int lch[N], rch[N], d[N], sz[N];
LL val[N], b[N];

int merge(int x, int y) {
  if(!x || !y)
    return x + y;
  if(val[x] < val[y])
    std::swap(x, y);
  sz[x] += sz[y];
  rch[x] = merge(rch[x], y);
  if(d[rch[x]] > d[lch[x]])
    std::swap(lch[x], rch[x]);
  d[x] = d[rch[x]] + 1;
  return x;
}

int dfs(int x, int y) {
  int rt = 0;
  for(int v: e[x])
    if(v != y) {
      int t = dfs(v, x);
      rt = merge(rt, t);
      b[x] += b[v];
    }
  LL now = a[x];
  while(sz[x] >= 2 && now < val[rt]) {
    now -= val[rt];
    rt = merge(lch[rt], rch[rt]);
    now += val[rt];
    rt = merge(lch[rt], rch[rt]);
  }
  if(now >= val[rt]) {
    val[x] = now;
    sz[x] = d[x] = 1;
    rt = merge(rt, x);
    return rt;
  }
  assert(sz[rt] == 1);
  b[x] += now - val[rt];
  return 0;
}

int main() {

  scanf("%d", &n);
  for(int i = 1; i <= n; ++i)
    scanf("%d", &a[i]);
  for(int i = 1, x, y; i < n; ++i) {
    scanf("%d%d", &x, &y);
    e[x].push_back(y);
    e[y].push_back(x);
  }

  val[0] = -1e18;
  int rt = dfs(1, 0);

  LL ans = (sz[rt] & 1 ? -b[1] : b[1]);
  for(int i = 1; rt; i = -i) {
    ans += i * val[rt];
    rt = merge(lch[rt], rch[rt]);
  }

  printf("%lld\n", ans);
  
  return 0; 

}
0