답안 #467798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
467798	2021-08-24T13:56:10 Z	ivan_tudor	Magic Tree (CEOI19_magictree)	C++14	100 / 100	159 ms	36980 KB

magictree

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> sons[N];
map<int, long long> dp[N];
pair<int, int> fruits[N];

void dfs(int nod){
  for(auto x: sons[nod]){
    dfs(x);
    if(dp[x].size() >  dp[nod].size())
      swap(dp[x], dp[nod]);
    for(auto vl : dp[x]){
      dp[nod][vl.first] += vl.second;
    }
  }
  if(fruits[nod].first == 0)
    return;
  long long d = fruits[nod].first, w = fruits[nod].second;
  dp[nod][d] += w;
  auto itr = dp[nod].upper_bound(d);
  while(itr != dp[nod].end() && w > 0){
    long long todel = min((*itr).second, w);
    w -= todel;
    (*itr).second -= todel;
    if((*itr).second == 0){
      itr = dp[nod].erase(itr);
    }
  }

}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n, m, k;
  cin>>n>>m>>k;
  for(int i = 2; i<=n; i++){
    int p;
    cin>>p;
    sons[p].push_back(i);
  }
  for(int i = 1; i <= m; i++){
    int v, d, w;
    cin>>v>>d>>w;
    fruits[v] = {d, w};
  }
  dfs(1);
  long long ans = 0;
  for(auto x: dp[1])
    ans += x.second;
  cout<<ans;
  return 0;
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	7372 KB	Output is correct
2	Correct	5 ms	7244 KB	Output is correct
3	Correct	5 ms	7244 KB	Output is correct
4	Correct	5 ms	7244 KB	Output is correct
5	Correct	5 ms	7244 KB	Output is correct
6	Correct	5 ms	7272 KB	Output is correct
7	Correct	6 ms	7360 KB	Output is correct
8	Correct	5 ms	7372 KB	Output is correct
9	Correct	5 ms	7320 KB	Output is correct

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	76 ms	18372 KB	Output is correct
2	Correct	49 ms	18972 KB	Output is correct
3	Correct	157 ms	36980 KB	Output is correct
4	Correct	94 ms	19916 KB	Output is correct
5	Correct	141 ms	21724 KB	Output is correct

Subtask #3
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	7412 KB	Output is correct
2	Correct	5 ms	7432 KB	Output is correct
3	Correct	6 ms	7548 KB	Output is correct
4	Correct	61 ms	25700 KB	Output is correct
5	Correct	84 ms	29640 KB	Output is correct
6	Correct	76 ms	25668 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	78 ms	15500 KB	Output is correct
2	Correct	76 ms	14656 KB	Output is correct
3	Correct	70 ms	18888 KB	Output is correct
4	Correct	50 ms	15816 KB	Output is correct
5	Correct	59 ms	25900 KB	Output is correct

Subtask #5
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	7372 KB	Output is correct
2	Correct	5 ms	7244 KB	Output is correct
3	Correct	5 ms	7244 KB	Output is correct
4	Correct	5 ms	7244 KB	Output is correct
5	Correct	5 ms	7244 KB	Output is correct
6	Correct	5 ms	7272 KB	Output is correct
7	Correct	6 ms	7360 KB	Output is correct
8	Correct	5 ms	7372 KB	Output is correct
9	Correct	5 ms	7320 KB	Output is correct
10	Correct	89 ms	17740 KB	Output is correct
11	Correct	91 ms	16644 KB	Output is correct
12	Correct	79 ms	18184 KB	Output is correct
13	Correct	46 ms	15188 KB	Output is correct
14	Correct	56 ms	25200 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	8140 KB	Output is correct
2	Correct	34 ms	10436 KB	Output is correct
3	Correct	38 ms	10468 KB	Output is correct
4	Correct	43 ms	10436 KB	Output is correct
5	Correct	15 ms	8780 KB	Output is correct
6	Correct	32 ms	12620 KB	Output is correct
7	Correct	35 ms	16212 KB	Output is correct

Subtask #7
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	7372 KB	Output is correct
2	Correct	5 ms	7244 KB	Output is correct
3	Correct	5 ms	7244 KB	Output is correct
4	Correct	5 ms	7244 KB	Output is correct
5	Correct	5 ms	7244 KB	Output is correct
6	Correct	5 ms	7272 KB	Output is correct
7	Correct	6 ms	7360 KB	Output is correct
8	Correct	5 ms	7372 KB	Output is correct
9	Correct	5 ms	7320 KB	Output is correct
10	Correct	5 ms	7412 KB	Output is correct
11	Correct	5 ms	7432 KB	Output is correct
12	Correct	6 ms	7548 KB	Output is correct
13	Correct	61 ms	25700 KB	Output is correct
14	Correct	84 ms	29640 KB	Output is correct
15	Correct	76 ms	25668 KB	Output is correct
16	Correct	89 ms	17740 KB	Output is correct
17	Correct	91 ms	16644 KB	Output is correct
18	Correct	79 ms	18184 KB	Output is correct
19	Correct	46 ms	15188 KB	Output is correct
20	Correct	56 ms	25200 KB	Output is correct
21	Correct	24 ms	10700 KB	Output is correct
22	Correct	87 ms	18664 KB	Output is correct
23	Correct	88 ms	21920 KB	Output is correct
24	Correct	136 ms	30216 KB	Output is correct
25	Correct	99 ms	19276 KB	Output is correct
26	Correct	124 ms	21060 KB	Output is correct
27	Correct	87 ms	20096 KB	Output is correct

Subtask #8
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	7372 KB	Output is correct
2	Correct	5 ms	7244 KB	Output is correct
3	Correct	5 ms	7244 KB	Output is correct
4	Correct	5 ms	7244 KB	Output is correct
5	Correct	5 ms	7244 KB	Output is correct
6	Correct	5 ms	7272 KB	Output is correct
7	Correct	6 ms	7360 KB	Output is correct
8	Correct	5 ms	7372 KB	Output is correct
9	Correct	5 ms	7320 KB	Output is correct
10	Correct	76 ms	18372 KB	Output is correct
11	Correct	49 ms	18972 KB	Output is correct
12	Correct	157 ms	36980 KB	Output is correct
13	Correct	94 ms	19916 KB	Output is correct
14	Correct	141 ms	21724 KB	Output is correct
15	Correct	5 ms	7412 KB	Output is correct
16	Correct	5 ms	7432 KB	Output is correct
17	Correct	6 ms	7548 KB	Output is correct
18	Correct	61 ms	25700 KB	Output is correct
19	Correct	84 ms	29640 KB	Output is correct
20	Correct	76 ms	25668 KB	Output is correct
21	Correct	78 ms	15500 KB	Output is correct
22	Correct	76 ms	14656 KB	Output is correct
23	Correct	70 ms	18888 KB	Output is correct
24	Correct	50 ms	15816 KB	Output is correct
25	Correct	59 ms	25900 KB	Output is correct
26	Correct	89 ms	17740 KB	Output is correct
27	Correct	91 ms	16644 KB	Output is correct
28	Correct	79 ms	18184 KB	Output is correct
29	Correct	46 ms	15188 KB	Output is correct
30	Correct	56 ms	25200 KB	Output is correct
31	Correct	9 ms	8140 KB	Output is correct
32	Correct	34 ms	10436 KB	Output is correct
33	Correct	38 ms	10468 KB	Output is correct
34	Correct	43 ms	10436 KB	Output is correct
35	Correct	15 ms	8780 KB	Output is correct
36	Correct	32 ms	12620 KB	Output is correct
37	Correct	35 ms	16212 KB	Output is correct
38	Correct	24 ms	10700 KB	Output is correct
39	Correct	87 ms	18664 KB	Output is correct
40	Correct	88 ms	21920 KB	Output is correct
41	Correct	136 ms	30216 KB	Output is correct
42	Correct	99 ms	19276 KB	Output is correct
43	Correct	124 ms	21060 KB	Output is correct
44	Correct	87 ms	20096 KB	Output is correct
45	Correct	26 ms	11088 KB	Output is correct
46	Correct	84 ms	19752 KB	Output is correct
47	Correct	102 ms	23292 KB	Output is correct
48	Correct	159 ms	33272 KB	Output is correct
49	Correct	92 ms	19924 KB	Output is correct
50	Correct	121 ms	22084 KB	Output is correct
51	Correct	101 ms	20900 KB	Output is correct

답안 #467798

Compilation message