Submission #313516

#	Time	Username	Problem	Language	Result	Execution time	Memory
313516		kylych03	Friend (IOI14_friend)	C++14	46 / 100	241 ms	65540 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
// Find out best sample
bool f[3];
vector <int> g[100001];
int dp[100001][2];
int con[100001];
int vis[100001];
int cnt ;
int cnt1;
void dfs1(int v, int p, int x){
    cnt++;
    cnt1+=(x%2);
    vis[v]=1;
    for(auto to : g[v] ){
        if(to==p || vis[p])
            continue;
        dfs1(to, v, x+1);
    }

}
void dfs(int v, int p){

    int ans1=0, ans2=0;
    for(auto to : g[v] ){
        if(to==p)
            continue;
        dfs(to, v);
        ans1+=dp[to][0];
        ans2+=max(dp[to][0], dp[to][1]);
    }
    dp[v][1] = max( ans1 + con[v], ans2);
    dp[v][0] = ans2;
}
int findSample(int n,int confidence[],int host[],int protocol[]){
	int  sum=0, mx=0;
    f[0]=f[1]=f[2]=false;
    bool flag=true;
	for(int i = 1 ; i < n;i++){
        f[protocol[i]]=true;
	}
	for(int i =0; i < n; i++){
        con[i]=confidence[i];
        if(con[i]!=1)
            flag=false;
        sum +=confidence[i];
        mx = max(mx, confidence[i] );
	}

	if( f[0]==false && f[2]==false )
        return sum;
    if( f[0]==false && f[1]==false )
        return mx;

    for(int  i = 1 ; i <n ;i++){
        if(protocol[i]==0){
            g[host[i]].push_back(i);
            g[i].push_back(host[i]);

        }
        if(protocol[i]==1){
             for(auto j : g[host[i]]){
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
        if(protocol[i]==2){
            for(auto j : g[host[i]]){
                g[i].push_back(j);
                g[j].push_back(i);
            }
            g[host[i]].push_back(i);
            g[i].push_back(host[i]);
        }
    }
    if( f[1]==false && f[2]==false ){

        dfs(0,-1);
        return max(dp[0][0], dp[0][1]);
    }
    if(n<=10){
        for(int j = 0 ;  j< (1<<n) ;j++){
            bool res=true;
            sum = 0;
            for(int  k = 0; k < n ;k++){
                if(j & (1<<k)){
                    sum+=confidence[k];
                    for(int t = k+1 ; t < n; t++){
                        if(j &(1 << t)){
                            for(int  s:g[k])
                            if(s==t){
                                res=false;
                                break;
                            }
                        }
                    }
                }
            }
            if(res)
                mx = max (mx, sum);
        }

        return mx;
    }
    if(flag){
            int sum =0;
        for(int i = 0 ; i  < n ; i++){
            if(vis[i]==0){
                cnt = 0 ;
                cnt1 =0;
                dfs1(i, -1, 0);
                sum+=max(cnt -cnt1, cnt1);
            }
        }
        return sum;

    }

}

Compilation message (stderr)

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

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