Submission #110621

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
110621	2019-05-11T14:54:33 Z	The_Wolfpack	Friend (IOI14_friend)	C++14	16 / 100	16 ms	4480 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Incorrect	3 ms	384 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	4 ms	384 KB	Output is correct

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1280 KB	Output is correct
2	Correct	13 ms	4224 KB	Output is correct
3	Correct	2 ms	512 KB	Output is correct
4	Correct	8 ms	3200 KB	Output is correct
5	Correct	14 ms	4224 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	4 ms	1024 KB	Output is correct
8	Correct	3 ms	1152 KB	Output is correct
9	Correct	3 ms	512 KB	Output is correct
10	Correct	16 ms	4480 KB	Output is correct