Submission #1220895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220895		Trumling	Magic Tree (CEOI19_magictree)	C++20	47 / 100	541 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<vector<ll>>g2;

vector<pair<ll,ll>>f;
vector<pair<ll,ll>>f2;
vector<vector<ll>>d;
ll k;
ll id=1;
void dfs1(int start,int pre,int prev)
{
    if(f[start].F!=0)
    {
        g2[id].pb(prev);
        g2[prev].pb(id);
        f2[id]=f[start];
        prev=id++;
    }
    for(auto x:g[start])
        if(x!=pre)
            dfs1(x,start,prev);
}
void dfs(int start,int pre)
{
    d[start][f2[start].F]=f2[start].S;

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


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});


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};
    }
d.assign(m+1,vector<ll>(k+1,0));
g2.assign(m+1,vector<ll>());
f2.assign(m+1,{0,0});
dfs1(1,1,0);

dfs(0,0);
ll ans=0;
for(int i=1;i<=k;i++)
    ans=max(ans,d[0][i]);
cout<<ans;
}

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