제출 #1269104

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269104		DangKhoizzzz	Magic Tree (CEOI19_magictree)	C++20	100 / 100	75 ms	31556 KiB

magictree

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18;
const int maxn = 2e5 + 7;

int n , m , k , d[maxn] , w[maxn];
vector <int> g[maxn];


map <int , int> dfs(int u , int p)
{
    map <int , int> res;
    for(int v: g[u])
    {
        if(v == p) continue;
        map <int , int> con = dfs(v , u);
        if(res.size() < con.size()) swap(res , con);
        for(pii tmp: con) res[tmp.fi] += tmp.se;
    }
    if(d[u])
    {
        res[d[u]] += w[u];
        auto it = res.upper_bound(d[u]);
        while(it != res.end())
        {
            if((*it).se > w[u])
            {
                (*it).se -= w[u];
                break;
            }
            else 
            {
                w[u] -= (*it).se;
                res.erase(it);
                it = res.upper_bound(d[u]);
            }
        }
    }
    return res;
}

void solve()
{
    cin >> n >> m >> k;
    for(int i = 2; i <= n; i++)
    {
        int p; cin >> p;
        g[p].push_back(i);
    }
    for(int i = 1; i <= m; i++)
    {
        int v; cin >> v;
        cin >> d[v] >> w[v];
    }
    map <int , int> res = dfs(1 , 1);
    int ans = 0;
    for(pii tmp: res) ans += tmp.se;
    cout << ans << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17