Submission #110621

#	Time	Username	Problem	Language	Result	Execution time	Memory
110621		The_Wolfpack	Friend (IOI14_friend)	C++14	16 / 100	16 ms	4480 KiB

friend

#include <bits/stdc++.h>
using namespace std;
const int NMAX=2007;

int cnt[3],vis[NMAX],w[NMAX],dp[NMAX][2];    
vector<int> g[NMAX];

int ans=0;
void dfs(int son, int par)
{
    vis[son]=1;
    ans=max(ans,w[son]);
    for(int i:g[son]) if(!vis[i]) dfs(i,son);
}

void dfs1(int son,int par)
{
    vis[son]=1;
    dp[son][1]=w[son];
    for(int i:g[son])
    {
        if(vis[i]) continue; 
        dfs1(i,son);
        dp[son][0]+=max(dp[i][0],dp[i][1]);
        dp[son][1]+=dp[i][0];
    }
}

int findSample(int n, int confidence[], int host[], int protocol[])
{
    cin>>n; 
    for(int i=0;i<n;i++) cin>>confidence[i], w[i]=confidence[i];
    for(int i=1;i<n;i++) 
    {
        cin>>host[i]>>protocol[i];
        int tmp=protocol[i];
        if(tmp==0)
        {
            cnt[0]++;
            g[host[i]].push_back(i);
            g[i].push_back(host[i]);
        }
        if(tmp==1)
        {
            cnt[1]++;
            for(int j:g[host[i]])
            {
                g[i].push_back(j);
                g[j].push_back(i);     
            }
        }
        else
        {
            cnt[2]++;
            g[host[i]].push_back(i);
            g[i].push_back(host[i]);
            for(int j:g[host[i]])
            {
                if(i==j) continue; 
                g[i].push_back(j);
                g[j].push_back(i);     
            }
        }
    }
    if(n<=10)
    {
        int res=0; 
        for(int mask=1;mask<(1<<11)+1;mask++)
        {
            vector<int> tmp;
            for(int i=0;i<n;i++) if(mask&(1<<i)) tmp.push_back(i);
            int ok=1;
            
            for(int i:tmp)
            {
                for(int j:tmp)
                {
                    if(i==j) continue; 
                    for(int t:g[i]) if(t==j) ok=0;
                }
            }
            
            int ans=0;
            if(ok) for(int i:tmp) ans+=confidence[i];
            if(ok) res=max(res,ans);
        }
        return res;
    }
    if(cnt[2]==n-1)
    {
        int res=0;
        ans=0;
        for(int i=0;i<n;i++) if(!vis[i]){dfs(i,0); res+=ans;}
        return res;
    }
    if(cnt[1]==n-1)
    {
        int res=0;
        for(int i=0;i<n;i++) res+=w[i];
        return res;
    }
    if(cnt[0]==n-1)
    {
        int res=0;
        for(int i=0;i<n;i++) if(!vis[i]){dfs1(i,0); res+=max(dp[i][0],dp[i][1]);}
        return res;
    }
}

Compilation message (stderr)

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:108:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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