Submission #995370

#	Time	Username	Problem	Language	Result	Execution time	Memory
995370		PagodePaiva	Jobs (BOI24_jobs)	C++17	11 / 100	165 ms	28148 KiB

Main

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int N = 300010;
vector <int> g[N];
vector <int> raizes;
int val[N];
int dp[N];

int dfs(int v, int p){
    int con = 0;
    for(auto x : g[v]){
        if(x == p) continue;
        dfs(x, v);
        con++;
    }
    if(con == 0)
        return dp[v] = max(0LL, val[v]);
    int vl = val[v];
    for(auto x : g[v]){
        if(x == p) continue;
        vl += dp[x];
    }
    dp[v] = max(vl, 0LL);
    return dp[v];
}

int32_t main(){
    int n, c;
    cin >> n >> c;
    if(c >= 1e18){
        for(int i = 1;i <= n;i++){
            int p;
            cin >> val[i] >> p;
            if(p == 0) raizes.push_back(i);
            else g[p].push_back(i);
        }
        int res = 0;
        for(auto x : raizes){
            res += dfs(x, x);
        }
        cout << res << '\n';
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31