Submission #155974

#	Time	Username	Problem	Language	Result	Execution time	Memory
155974		Alexa2001	Friend (IOI14_friend)	C++17	100 / 100	37 ms	3504 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e5 + 5;
int p[Nmax], q[Nmax];

int findSample(int n, int confidence[], int host[], int protocol[])
{
    int i;
    for(i=0; i<n; ++i) p[i] = confidence[i], q[i] = 0;

    for(i=n-1; i; --i)
    {
        int newp, newq, id = host[i];

        if(protocol[i] == 0) /// IAmYourFriend
        {
            newp = p[id] + q[i];
            newq = q[id] + p[i];
        }
        else if(protocol[i] == 1) /// MyFriendsAreYourFriends
        {
            newp = p[id] + p[i];
            newq = q[i] + q[id];
        }
        else /// WeAreYourFriends
        {
            newp = max(p[id] + q[i], p[i] + q[id]);
            newq = q[i] + q[id];
        }

        p[id] = max(newq, newp);
        q[id] = newq;
    }
    return p[0];
}

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