Submission #19203171


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<int64_t> C(N, INT64_MAX);
  C[0] = 0;
  queue<int> que;
  rep(i, M) {
    int b, c;
    cin >> b >> c;
    C[b] = c;
    que.emplace(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[parent[u]] == 0)
        que.emplace(parent[u]);
    }
  }

  int64_t 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 300
Code Size 1018 Byte
Status AC
Exec Time 8 ms
Memory 3708 KB

Judge Result

Set Name All
Score / Max Score 300 / 300
Status
AC × 27
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 3504 KB
00_sample_2 AC 2 ms 3516 KB
00_sample_3 AC 2 ms 3512 KB
10_random_00_n_5 AC 2 ms 3620 KB
10_random_01_n_10 AC 2 ms 3648 KB
10_random_02_n_2 AC 2 ms 3620 KB
10_random_03_n_7 AC 2 ms 3604 KB
10_random_04_n_6 AC 2 ms 3576 KB
20_random_00_n_64 AC 2 ms 3520 KB
20_random_01_n_95 AC 2 ms 3580 KB
20_random_02_n_20 AC 2 ms 3464 KB
20_random_03_n_33 AC 2 ms 3464 KB
20_random_04_n_91 AC 2 ms 3616 KB
30_random_00_n_793 AC 2 ms 3708 KB
30_random_01_n_611 AC 3 ms 3660 KB
30_random_02_n_852 AC 2 ms 3676 KB
40_random_00_n_1000 AC 2 ms 3632 KB
40_random_01_n_1000 AC 2 ms 3664 KB
50_edge_one_00_n_11 AC 2 ms 3524 KB
50_edge_one_01_n_101 AC 2 ms 3632 KB
50_edge_one_02_n_999 AC 2 ms 3708 KB
98_almost_straight_00_n_1000 AC 3 ms 3680 KB
98_almost_straight_01_n_1000 AC 2 ms 3652 KB
98_almost_straight_02_n_1000 AC 2 ms 3648 KB
99_straight_00_n_10 AC 2 ms 3656 KB
99_straight_01_n_100 AC 2 ms 3512 KB
99_straight_02_n_1000 AC 2 ms 3644 KB