Submission #285939

#	Time	Username	Problem	Language	Result	Execution time	Memory
285939		evpipis	Friend (IOI14_friend)	C++11	100 / 100	37 ms	3456 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
using namespace std;

const int len = 1e5+5;
int yes[len], no[len];

int findSample(int n, int con[], int host[], int prot[]){
	for (int i = 0; i < n; i++)
        yes[i] = con[i], no[i] = 0;

    for (int y = n-1; y > 0; y--){
        int x = host[y], tp = prot[y];
        int p = 0, q = 0;

        // case IAmYourFriend
        if (tp == 0){
            p = yes[x]+no[y];
            q = max(no[x]+no[y], no[x]+yes[y]);
        }
        // case MyFriendsAreYourFriends
        else if (tp == 1){
            q = no[x]+no[y];
            p = yes[x]+yes[y];
            p = max(p, no[x]+yes[y]);
            p = max(p, yes[x]+no[y]);
        }
        // case WeAreYourFriends
        else{
            q = no[x]+no[y];
            p = max(yes[x]+no[y], no[x]+yes[y]);
        }

        yes[x] = p;
        no[x] = q;
    }

	return max(yes[0], no[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