Submission #295575

#	Time	Username	Problem	Language	Result	Execution time	Memory
295575		stoyan_malinin	Friend (IOI14_friend)	C++14	11 / 100	51 ms	6392 KiB

friend

#include "friend.h"
//#include "grader.cpp"

#include <vector>
#include <iostream>

using namespace std;

const int MAXN = 1005;

int n;
vector <int> graph[MAXN];

void constructGrahp(int n, int confidence[], int host[], int protocol[])
{
    for(int x = 1;x<=n;x++)
    {
        if(protocol[x]==0)
        {
            graph[ host[x] ].push_back(x);
            graph[x].push_back(host[x]);
        }
        else if(protocol[x]==1)
        {
            for(int y: graph[ host[x] ])
            {
                graph[y].push_back(x);
                graph[x].push_back(y);
            }
        }
        else if(protocol[x]==2)
        {
            graph[x].push_back(host[x]);
            graph[ host[x] ].push_back(x);

            for(int y: graph[ host[x] ])
            {
                graph[y].push_back(x);
                graph[x].push_back(y);
            }
        }
    }
}

namespace Subtask1
{
    bool can(int x, int mask)
    {
        for(int y: graph[x])
        {
            if(((mask>>y)&1)==1) return false;
        }

        return true;
    }

    int rec(int x, int mask, int confidence[])
    {
        if(x==n) return 0;

        int answer = rec(x+1, mask, confidence);
        if(can(x, mask)==true) answer = max(answer, confidence[x]+rec(x+1, (mask|(1<<x)), confidence));

        return answer;
    }

    int solve(int n, int confidence[], int host[], int protocol[])
    {
        return rec(0, 0, confidence);
    }
};

int guessSubtask()
{
    if(n<=10) return 1;

    return -1;
}

int findSample(int _n,int confidence[],int host[],int protocol[])
{
    n = _n;
    constructGrahp(n, confidence, host, protocol);

    if(guessSubtask()==1) return Subtask1::solve(n, confidence, host, protocol);

    return 0;
}

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