# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
995446 |
2024-06-09T06:00:57 Z |
12345678 |
Jobs (BOI24_jobs) |
C++17 |
|
84 ms |
30544 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=3e5+5;
ll n, s, vs[nx], c[nx], p, dp[nx], res;
vector<ll> d[nx];
void dfs(int u)
{
vs[u]=1;
ll sm=c[u];
for (auto v:d[u]) dfs(v), sm+=dp[v];
dp[u]=max(0ll, sm);
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>s;
for (int i=1; i<=n; i++)
{
cin>>c[i]>>p;
if (p!=0) d[p].push_back(i);
}
for (int i=1; i<=n; i++) if (!vs[i]) dfs(i), res+=dp[i];
cout<<res;
}
/*
6 1
3 0
-3 1
-5 0
2 1
6 3
-4 5
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
84 ms |
22640 KB |
Output is correct |
2 |
Correct |
84 ms |
21840 KB |
Output is correct |
3 |
Correct |
64 ms |
20560 KB |
Output is correct |
4 |
Correct |
67 ms |
27216 KB |
Output is correct |
5 |
Correct |
61 ms |
30032 KB |
Output is correct |
6 |
Correct |
47 ms |
16720 KB |
Output is correct |
7 |
Correct |
74 ms |
21584 KB |
Output is correct |
8 |
Correct |
70 ms |
20560 KB |
Output is correct |
9 |
Correct |
53 ms |
29012 KB |
Output is correct |
10 |
Correct |
58 ms |
30544 KB |
Output is correct |
11 |
Correct |
74 ms |
21844 KB |
Output is correct |
12 |
Correct |
73 ms |
19536 KB |
Output is correct |
13 |
Correct |
73 ms |
21840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
7512 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
7512 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
7512 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
84 ms |
22640 KB |
Output is correct |
2 |
Correct |
84 ms |
21840 KB |
Output is correct |
3 |
Correct |
64 ms |
20560 KB |
Output is correct |
4 |
Correct |
67 ms |
27216 KB |
Output is correct |
5 |
Correct |
61 ms |
30032 KB |
Output is correct |
6 |
Correct |
47 ms |
16720 KB |
Output is correct |
7 |
Correct |
74 ms |
21584 KB |
Output is correct |
8 |
Correct |
70 ms |
20560 KB |
Output is correct |
9 |
Correct |
53 ms |
29012 KB |
Output is correct |
10 |
Correct |
58 ms |
30544 KB |
Output is correct |
11 |
Correct |
74 ms |
21844 KB |
Output is correct |
12 |
Correct |
73 ms |
19536 KB |
Output is correct |
13 |
Correct |
73 ms |
21840 KB |
Output is correct |
14 |
Incorrect |
3 ms |
7512 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |