Submission #748201

#	Time	Username	Problem	Language	Result	Execution time	Memory
748201		Username4132	Friend (IOI14_friend)	C++14	35 / 100	2 ms	2772 KiB

friend

#include "friend.h"
#include<iostream>
#include<vector>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back

const int MAXN=100010;
int n, dp[2][MAXN], conf[MAXN];
vector<int> g[MAXN];

void dfs(int v, int p){
	dp[1][v]=conf[v];
	for(int to:g[v]) if(to!=p) {
		dfs(to, v);
		dp[1][v]+=dp[0][to];
		dp[0][v]+=dp[1][to];
	}
	dp[1][v]=max(dp[0][v], dp[1][v]);
}

int solve0(int confidence[], int host[]){
	forsn(i, 1, n) g[i].PB(host[i]), g[host[i]].PB(i);
	dfs(0, 0);
	return dp[1][0];
}

int solve1(int confidence[], int host[]){
	int sum=0;
	forn(i, n) sum+=confidence[i];
	return sum;
}

int solve2(int confidence[], int host[]){
	int mx=-1;
	forn(i, n) mx=max(mx, confidence[i]);
	return mx;
}

int solveTask(int task, int confidence[], int host[]){
	if(task==0) return solve0(confidence, host);
	else if(task==1) return solve1(confidence, host);
	else if(task==2) return solve2(confidence, host);
}

// Find out best sample
int findSample(int N, int confidence[], int host[], int protocol[]){
	n=N;
	forn(i, n) conf[i]=confidence[i];
	bool eq=true;
	forsn(i, 1, n-1) eq&=protocol[i]==protocol[i+1];
	if(eq) return solveTask(protocol[1], confidence, host);

	return 0;
}

Compilation message (stderr)

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

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