Submission #1220853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220853		Trumling	Magic Tree (CEOI19_magictree)	C++20	0 / 100	507 ms	1114112 KiB

magictree

//Trumling ©
//Αφόδευε υψηλά και ηγνάντει 
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()

vector<vector<ll>>g;
vector<pair<ll,ll>>f;
vector<vector<ll>>d;
ll k;
void dfs(int start,int pre)
{
    d[start][f[start].F]=f[start].S;

    for(auto x:g[start])
        if(x!=pre)
        {
            dfs(x,start);
            for(int i=1;i<=k;i++)
                d[start][i]+=d[x][i];
        }
}

void dfs2(int start,int pre,ll &get,ll day)
{
    ll maxi=-1,maxid=-1;
    for(int i=1;i<day;i++)
        if(d[start][i] - d[start][day] >= maxi)
            {
                maxi=d[start][i] - d[start][day];
                maxid=i;
            }
    
       
    
    if(maxid!=-1)
    {
        get+=maxi;
        day=maxid;
    }

            
    for(auto x:g[start])
        if(x!=pre)
            dfs2(x,start,get,day);     
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n,m;
cin>>n>>m>>k;
g.assign(n+1,vector<ll>());
f.assign(n+1,{0,0});
d.assign(n+1,vector<ll>(k+1,0));
for(int i=2;i<=n;i++)
{
    ll x;
    cin>>x;
    g[i].pb(x);
    g[x].pb(i);
}

for(int i=0;i<m;i++)
    {
        ll x,y,z;
        cin>>x>>y>>z;
        f[x]={y,z};
    }
dfs(1,1);
ll ans=0;
for(auto x:g[1])
{
    ll curr=d[x][k];
    dfs2(x,1,curr,k);
    ans+=curr;
}
cout<<ans;
}

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