Submission #1360909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1360909		ziyad_alharbi	Magic Tree (CEOI19_magictree)	C++20	0 / 100	2096 ms	24016 KiB

magictree

#include <bits/stdc++.h> 
using namespace std;
#define int long long
const int maxn=2e5+5;
vector<int>v[maxn];
int n,e,k,dp[maxn],fr[maxn],t[maxn];
set<array<int,2>>m[maxn];
int f(int x,int p)
{
    if(dp[x]!=-1)return dp[x];
    int s1=0,s2=0;
    if(t[x])m[x].insert({t[x],fr[x]});
    for(auto i:v[x])
    {
        if(i==p)continue;
        s1+=f(i,x);
        if(m[x].size()<m[i].size())swap(m[x],m[i]);
        while(m[i].size())
        {
            auto [j,vl]=*m[i].begin();
            m[i].erase({j,vl});
            auto [i,vl2]=*m[x].lower_bound({j,0});
            if(i==j)
            {
                vl+=vl2;
                m[x].erase({i,vl2});
            }
            m[x].insert({j,vl});
        }
    }
    for(auto [_,vl]:m[x])s2=max(s2,vl);
    return dp[x]=max(s1,s2);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>e>>k;
    dp[1]=dp[0]=-1;
    for(int x=2;x<=n;x++)
    {
        dp[x]=-1;
        int i;
        cin>>i;
        v[i].push_back(x);
        v[x].push_back(i);
    }
    for(int x=0;x<e;x++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        t[a]=b;
        fr[a]=c;
    }
    cout<<f(1,1)<<endl;
    return 0;
}
 

• 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