結果

問題 No.3283 Labyrinth and Friends
ユーザー tnakao0123
提出日時 2025-09-28 17:14:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 16 ms / 2,000 ms
コード長 1,513 bytes
コンパイル時間 3,360 ms
コンパイル使用メモリ 58,156 KB
実行使用メモリ 35,176 KB
最終ジャッジ日時 2025-09-28 17:14:18
合計ジャッジ時間 3,158 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:38:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   38 |   scanf("%d%d", &n, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~
main.cpp:40:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   40 |   for (int i = 1; i < n; i++) scanf("%d", ps + i), ps[i]--;
      |                               ~~~~~^~~~~~~~~~~~~~
main.cpp:42:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   42 |   for (int i = 1; i < n; i++) scanf("%d%d", cs + i, ss + i);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 3283.cc:  No.3283 Labyrinth and Friends - yukicoder
 */

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 2000;
const int MAX_X = 2000;
const long long LINF = 1LL << 62;

/* typedef */

using ll = long long;
using vi = vector<int>;

/* global variables */

int ps[MAX_N], cs[MAX_N], ss[MAX_N];
vi nbrs[MAX_N];
int cis[MAX_N], mxs[MAX_N];
ll dp[MAX_N][MAX_X + 1], tmp[MAX_X + 1];

/* subroutines */

inline void setmin(ll &a, ll b) { if (a > b) a = b; }

/* main */

int main() {
  int n, x;
  scanf("%d%d", &n, &x);
  ps[0] = -1;
  for (int i = 1; i < n; i++) scanf("%d", ps + i), ps[i]--;
  cs[0] = ss[0] = 0;
  for (int i = 1; i < n; i++) scanf("%d%d", cs + i, ss + i);

  for (int i = 1; i < n; i++) nbrs[ps[i]].push_back(i);
  
  for (int i = 0; i < n; i++) {
    fill(dp[i], dp[i] + x + 1, LINF);
    dp[i][0] = 0;
  }

  for (int u = 0; u >= 0;) {
    auto &nbru = nbrs[u];
    int up = ps[u];

    if (cis[u] < nbru.size()) {
      int v = nbru[cis[u]++];
      u = v;
    }
    else {
      if (up >= 0) {
	copy(dp[up], dp[up] + x + 1, tmp);
	for (int i = 0; i <= mxs[u]; i++)
	  if (dp[u][i] < LINF)
	    for (int j = 0; j <= mxs[up]; j++)
	      if (dp[up][j] < LINF)
		setmin(tmp[min(x, i + j + ss[u])],
		       dp[up][j] + dp[u][i] + cs[u]);
	mxs[up] = min(x, mxs[up] + mxs[u] + ss[u]);
	copy(tmp, tmp + x + 1, dp[up]);
      }
      
      u = up;
    }
  }

  printf("%lld\n", dp[0][x]);
  
  return 0;
}
0