제출 #295595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295595		stoyan_malinin	Friend (IOI14_friend)	C++14	19 / 100	41 ms	5244 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);
    }
};

namespace Subtask2
{
    int solve(int n, int confidence[], int host[], int protocol[])
    {
        int ans = 0;
        for(int x = 0;x<n;x++) ans += confidence[x];

        return ans;
    }
};

namespace Subtask3
{
    int solve(int n, int confidence[], int host[], int protocol[])
    {
        int ans = 0;
        for(int x = 0;x<n;x++) ans = max(ans, confidence[x]);

        return ans;
    }
};

int guessSubtask(int n, int confidence[], int host[], int protocol[])
{
    if(n<=10) return 1;

    bool subtask2 = true;
    for(int x = 1;x<n;x++)
    {
        if(protocol[x]!=1)
        {
            subtask2 = false;
            break;
        }
    }
    if(subtask2==true) return 2;

    bool subtask3 = true;
    for(int x = 1;x<n;x++)
    {
        if(protocol[x]!=2)
        {
            subtask3 = false;
            break;
        }
    }
    if(subtask3==true) return 2;

    return -1;
}

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

    int subtask = guessSubtask(n, confidence, host, protocol);
    if(subtask==1) return Subtask1::solve(n, confidence, host, protocol);
    else if(subtask==2) return Subtask2::solve(n, confidence, host, protocol);
    else if(subtask==3) return Subtask3::solve(n, confidence, host, protocol);

    return 0;
}

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