oj.uz

Submission #717120

# Submission time Handle Problem Language Result Execution time Memory
717120 2023-04-01T08:07:18 Z bin9638 Friend (IOI14_friend) C++17
100 / 100
 39 ms 7956 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 2 ms 2656 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2660 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 3 ms 2656 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 1 ms 2664 KB Output is correct
14 Correct 2 ms 2660 KB Output is correct
15 Correct 2 ms 2660 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2664 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 3 ms 2600 KB Output is correct
8 Correct 3 ms 2668 KB Output is correct
9 Correct 3 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2708 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2660 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2664 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 3 ms 2644 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2660 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2656 KB Output is correct
9 Correct 2 ms 2792 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2660 KB Output is correct
16 Correct 2 ms 2652 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2660 KB Output is correct
19 Correct 3 ms 2656 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2640 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2660 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2596 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 38 ms 7956 KB Output is correct
13 Correct 19 ms 5284 KB Output is correct
14 Correct 35 ms 7376 KB Output is correct
15 Correct 39 ms 7404 KB Output is correct