Submission #498046

#	Time	Username	Problem	Language	Result	Execution time	Memory
498046		andrei_boaca	Magic Tree (CEOI19_magictree)	C++17	100 / 100	1199 ms	17228 KiB

magictree

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long ll;
ll n,m,k,par[100005],niv[100005],dp[3][100005],val[100005],day[100005],minim[100005];
vector<int> muchii[100005];
struct date
{
    ll nod,day,val;
} v[100005];
void dfscontrol(int nod)
{
    if(nod==1)
        niv[nod]=1;
    for(int i=0;i<muchii[nod].size();i++)
    {
        int fiu=muchii[nod][i];
        par[fiu]=nod;
        niv[fiu]=niv[nod]+1;
        dfscontrol(fiu);
    }
}
bool comp(date a, date b)
{
    if(a.day!=b.day)
        return a.day<b.day;
    if(niv[a.nod]!=niv[b.nod])
        return niv[a.nod]>niv[b.nod];
    return 0;
}
bool comp1(date a, date b)
{
    return a.nod>b.nod;
}
void solve3()
{
    sort(v+1,v+m+1,comp1);
    for(int i=1;i<=1e5;i++)
        minim[i]=1e9;
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        int val=v[i].day;
        int st=0;
        int dr=i-1;
        int best=0;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(minim[mij]<=val)
            {
                best=mij;
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        ans=max(ans,best+1);
        minim[best+1]=min(minim[best+1],val*1LL);
    }
    cout<<ans<<'\n';
}
void dfs(int nod)
{
    for(int i=0;i<muchii[nod].size();i++)
    {
        int fiu=muchii[nod][i];
        dfs(fiu);
    }
    if(val[nod]!=0&&day[nod]!=0)
        for(int i=day[nod];i<=day[nod];i++)
            dp[i][nod]+=val[nod];
    for(int i=0;i<muchii[nod].size();i++)
    {
        int fiu=muchii[nod][i];
        for(int j=1;j<=k;j++)
            dp[j][nod]+=dp[j][fiu];
    }
    dp[2][nod]=max(dp[1][nod],dp[2][nod]);
}
void solve4()
{
    for(int i=1;i<=m;i++)
    {
        int nod=v[i].nod;
        day[nod]=v[i].day;
        val[nod]=v[i].val;
    }
    dfs(1);
    cout<<max(dp[1][1],dp[k][1])<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k;
    bool is3=1;
    for(int i=2;i<=n;i++)
    {
        int p;
        cin>>p;
        par[i]=p;
        if(par[i]!=i-1)
            is3=0;
        muchii[p].push_back(i);
    }
    for(int i=1;i<=m;i++)
        cin>>v[i].nod>>v[i].day>>v[i].val;
    dfscontrol(1);
    sort(v+1,v+m+1,comp);
    if(k<=2)
    {
        solve4();
        return 0;
    }
    if(is3)
    {
        solve3();
        return 0;
    }
    for(int i=1;i<=m;i++)
    {
        int nod=v[i].nod;
        ll x=v[i].val;
        dp[1][nod]=dp[0][nod]+x;
        while(nod!=1)
        {
            nod=par[nod];
            dp[0][nod]+=x;
            if(dp[0][nod]-x<=dp[1][nod]&&dp[0][nod]>dp[1][nod])
                x=dp[0][nod]-dp[1][nod];
            else if(dp[0][nod]<=dp[1][nod])
            {
                x=0;
                break;
            }
        }
    }
    cout<<dp[0][1];
    return 0;
}

Compilation message (stderr)

magictree.cpp: In function 'void dfscontrol(int)':
magictree.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=0;i<muchii[nod].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~
magictree.cpp: In function 'void dfs(int)':
magictree.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=0;i<muchii[nod].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~
magictree.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i=0;i<muchii[nod].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~

• 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