제출 #1017441

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1017441		vivkostov	Friend (IOI14_friend)	C++14	27 / 100	1099 ms	16060 KiB

friend

#include<bits/stdc++.h>
#define endl '\n'
#include "friend.h"
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n,a,b,br[1500][1500],mas[1500],otg,con[1500],ho[1500],pr[1500],s,ma;
void check()
{
    int seg=0;
    for(int i=0;i<n;i++)
    {
        if(!mas[i])continue;
        for(int j=i+1;j<n;j++)
        {
            if(!mas[j])continue;
            if(br[i][j])return;
        }
        seg+=con[i];
    }
    otg=max(otg,seg);
}
void rec(int step)
{
    if(step==n)
    {
        check();
        return;
    }
    for(int i=0;i<=1;i++)
    {
        mas[step]=i;
        rec(step+1);
    }
}
int findSample(int N, int confidence[], int host[], int protocol[])
{
    n=N;
    int br0=0,br1=0,br2=0;
    for(int i=1;i<n;i++)
    {
        if(protocol[i]==0)
        {
            br0++;
            br[host[i]][i]=1;
            br[i][host[i]]=1;
        }
        if(protocol[i]==1)
        {
            br1++;
            for(int j=0;j<n;j++)
            {
                br[i][j]=br[host[i]][j];
                br[j][i]=br[j][host[i]];
            }
        }
        if(protocol[i]==2)
        {
            br2++;
            for(int j=0;j<n;j++)
            {
                br[i][j]=br[host[i]][j];
                br[j][i]=br[j][host[i]];
            }
            br[host[i]][i]=1;
            br[i][host[i]]=1;
        }
    }
    for(int i=0;i<n;i++)
    {
        con[i]=confidence[i];
        s+=con[i];
        ma=max(con[i],ma);
    }
    if(br1==n-1)return s;
    if(br2==n-1)return ma;
    rec(0);
    return otg;
}
void read()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        cin>>ho[i]>>pr[i];
        if(pr[i]==0)
        {
            br[ho[i]][i]=1;
            br[i][ho[i]]=1;
        }
        if(pr[i]==1)
        {
            for(int j=0;j<n;j++)
            {
                br[i][j]=br[ho[i]][j];
                br[j][i]=br[j][ho[i]];
            }
        }
        if(pr[i]==2)
        {
            for(int j=0;j<n;j++)
            {
                br[i][j]=br[ho[i]][j];
                br[j][i]=br[j][ho[i]];
            }
            br[ho[i]][i]=1;
            br[i][ho[i]]=1;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            //cout<<br[i][j]<<" ";
        }
        //cout<<endl;
    }
    for(int i=0;i<n;i++)
    {
        cin>>con[i];
    }
    rec(0);
    cout<<otg<<endl;
}
/*int main()
{
    speed();
    read();
    return 0;
}
*/

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