Submission #1017472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017472		vivkostov	Friend (IOI14_friend)	C++14	46 / 100	48 ms	65536 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,dpin[1500],dpout[1500];
vector<int>v[1500];
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);
    }
}
void make_dp(int beg,int par)
{
    int w;
    int sout=0,sin=0;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(w==par)continue;
        if(!dpin[w])make_dp(w,beg);
        sin+=max(dpin[w],dpout[w]);
        sout+=dpout[w];
    }
    dpin[beg]=sout+con[beg];
    dpout[beg]=sin;
}
int findSample(int N, int confidence[], int host[], int protocol[])
{
    n=N;
    int br0=0,br1=0,br2=0,h;
    for(int i=1;i<n;i++)
    {
        h=host[i];
        if(protocol[i]==0)
        {
            br0++;
            br[h][i]=1;
            br[i][h]=1;
            v[h].push_back(i);
            v[i].push_back(h);
        }
        if(protocol[i]==1)
        {
            br1++;
            for(int j=0;j<n;j++)
            {
                br[i][j]=br[h][j];
                br[j][i]=br[j][h];
                if(br[h][j])v[i].push_back(j);
                if(br[j][h])v[j].push_back(i);
            }
        }
        if(protocol[i]==2)
        {
            br2++;
            for(int j=0;j<n;j++)
            {
                br[i][j]=br[h][j];
                br[j][i]=br[j][h];
                if(br[h][j])v[i].push_back(j);
                if(br[j][h])v[j].push_back(i);
            }
            br[h][i]=1;
            br[i][h]=1;
            v[h].push_back(i);
            v[i].push_back(h);
        }
    }
    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;
    if(n<=10)
    {
        rec(0);
        return otg;
    }
    else
    {
        make_dp(0,0);
        return max(dpin[0],dpout[0]);
    }
}
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;
}
*/

Compilation message (stderr)

friend.cpp: In function 'void make_dp(int, int)':
friend.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~

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