Submission #717120

#	Time	Username	Problem	Language	Result	Execution time	Memory
717120		bin9638	Friend (IOI14_friend)	C++17	100 / 100	39 ms	7956 KiB

friend

#include<bits/stdc++.h>

#ifndef SKY
#include "friend.h"
#endif // SKY

using namespace std;
#define N 100010
#define ll long long
#define ii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define iii pair<int,ii>

int n,a[N],dp[N][2];
vector<ii>g[N];

void selfmax(int&u,int v)
{
    u=max(u,v);
}

void DFS(int u,int p)
{
    dp[u][0]=dp[u][1]=0;
    for(auto v:g[u])
        if(v.sc!=p)
            DFS(v.sc,u);
    int f[2][2]={};
    f[0][1]=f[1][0]=f[1][1]=-1e9;
    for(auto v:g[u])
        if(v.sc!=p)
        {
            int tmp[2][2]={};
            for(int i=0;i<=1;i++)
                for(int j=0;j<=1;j++)
                    selfmax(tmp[i][j],f[i][j]+dp[v.sc][0]);
            if(v.fs==1)
            {
                for(int i=0;i<=1;i++)
                    for(int j=0;j<=1;j++)
                        selfmax(tmp[1][j],f[i][j]+dp[v.sc][1]);
            }
            if(v.fs==2)
            {
                for(int j=0;j<=1;j++)
                    selfmax(tmp[0][1],f[0][j]+dp[v.sc][1]);
            }
            if(v.fs==3)
            {
                 for(int j=0;j<=1;j++)
                    selfmax(tmp[1][1],f[0][j]+dp[v.sc][1]);
              //  cout<<u<<" "<<v.sc<<" "<<dp[v.sc][1]<<" "<<tmp[1][1]<<endl;
            }
            for(int i=0;i<=1;i++)
                for(int j=0;j<=1;j++)
                    f[i][j]=tmp[i][j];
            //cout<<"cc "<<u<<" "<<v.sc<<" "<<f[1][1]<<endl;
        }
    for(int j=1;j>=0;j--)
        selfmax(f[0][1],f[0][j]+a[u]);
    dp[u][0]=max(f[0][0],f[1][0]);
    dp[u][1]=max(f[0][1],f[1][1]);
  //  cout<<u<<" "<<dp[u][0]<<" "<<dp[u][1]<<endl;
}

int findSample(int cc,int cost[],int host[],int protocol[])
{
    n=cc;
    for(int i=0;i<n;i++)
        a[i]=cost[i],g[i].clear();
    for(int i=1;i<n;i++)
    {
      //  cout<<host[i]<<" "<<i<<" "<<protocol[i]<<endl;
        g[host[i]].pb({protocol[i]+1,i});
    }
    DFS(0,-1);
    return max(dp[0][0],dp[0][1]);
}


#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    int a[n],host[n],protocol[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>host[i];
    for(int i=0;i<n;i++)
        cin>>protocol[i];
    cout<<findSample(n,a,host,protocol);
    return 0;
}
#endif // SKY

• Subtask 1: 11 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31