Submission #19202945


Source Code Expand

Copy
#include <iostream>
#include <queue>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int main(void) {
  ios::sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<int> parent(N);
  vector<vector<int>> child(N);
  vector<int> inEdge(N, 0);
  rep(i, N-1) {
    cin >> parent[i+1];
    child[parent[i+1]].emplace_back(i+1);
    inEdge[parent[i+1]]++;
  }
  vector<int> B(M);
  vector<int> C(N, INT32_MAX);
  C[0] = 0;
  queue<int> que;
  rep(i, M) {
    int b, c;
    cin >> b >> c;
    C[b] = c;
    C[parent[b]] = min(C[parent[b]], c);
    inEdge[parent[b]]--;
    if(inEdge[parent[b]] == 0)
      que.emplace(parent[b]);
  }

  while(!que.empty()) {
    int size = que.size();
    rep(i, size) {
      auto u = que.front();
      que.pop();
      if(u == 0) break;
      for(auto& v : child[u]) C[v] -= C[u];
      C[parent[u]] = min(C[parent[u]], C[u]);
      inEdge[parent[u]]--;
      if(inEdge[u] == 0)
        que.emplace(parent[u]);
    }
  }

  int answer = 0;
  rep(i, N) answer += C[i];
  cout << answer << endl;
  return 0;
}

Submission Info

Submission Time
Task B - PackDrop
User ysfk
Language C++ (GCC 9.2.1)
Score 0
Code Size 1133 Byte
Status WA
Exec Time 8 ms
Memory 3616 KB

Judge Result

Set Name All
Score / Max Score 0 / 300
Status
AC × 16
WA × 11
Set Name Test Cases
All 00_sample_1, 00_sample_2, 00_sample_3, 10_random_00_n_5, 10_random_01_n_10, 10_random_02_n_2, 10_random_03_n_7, 10_random_04_n_6, 20_random_00_n_64, 20_random_01_n_95, 20_random_02_n_20, 20_random_03_n_33, 20_random_04_n_91, 30_random_00_n_793, 30_random_01_n_611, 30_random_02_n_852, 40_random_00_n_1000, 40_random_01_n_1000, 50_edge_one_00_n_11, 50_edge_one_01_n_101, 50_edge_one_02_n_999, 98_almost_straight_00_n_1000, 98_almost_straight_01_n_1000, 98_almost_straight_02_n_1000, 99_straight_00_n_10, 99_straight_01_n_100, 99_straight_02_n_1000
Case Name Status Exec Time Memory
00_sample_1 AC 8 ms 3604 KB
00_sample_2 AC 2 ms 3496 KB
00_sample_3 AC 3 ms 3492 KB
10_random_00_n_5 AC 2 ms 3556 KB
10_random_01_n_10 WA 2 ms 3560 KB
10_random_02_n_2 AC 2 ms 3604 KB
10_random_03_n_7 AC 2 ms 3544 KB
10_random_04_n_6 AC 3 ms 3548 KB
20_random_00_n_64 WA 2 ms 3552 KB
20_random_01_n_95 WA 2 ms 3540 KB
20_random_02_n_20 WA 2 ms 3548 KB
20_random_03_n_33 WA 3 ms 3528 KB
20_random_04_n_91 WA 2 ms 3580 KB
30_random_00_n_793 WA 2 ms 3540 KB
30_random_01_n_611 WA 2 ms 3568 KB
30_random_02_n_852 WA 2 ms 3500 KB
40_random_00_n_1000 WA 3 ms 3604 KB
40_random_01_n_1000 WA 3 ms 3616 KB
50_edge_one_00_n_11 AC 2 ms 3608 KB
50_edge_one_01_n_101 AC 3 ms 3564 KB
50_edge_one_02_n_999 AC 3 ms 3600 KB
98_almost_straight_00_n_1000 AC 2 ms 3612 KB
98_almost_straight_01_n_1000 AC 2 ms 3552 KB
98_almost_straight_02_n_1000 AC 6 ms 3564 KB
99_straight_00_n_10 AC 4 ms 3500 KB
99_straight_01_n_100 AC 2 ms 3504 KB
99_straight_02_n_1000 AC 3 ms 3516 KB