oj.uz

Submission #995446

# Submission time Handle Problem Language Result Execution time Memory
995446 2024-06-09T06:00:57 Z 12345678 Jobs (BOI24_jobs) C++17
11 / 100
 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
*/

Subtask #1
11.0 / 11.0

# 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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 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 -