Submission #131434

#	Time	Username	Problem	Language	Result	Execution time	Memory
131434		MAMBA	Friend (IOI14_friend)	C++17	100 / 100	66 ms	8200 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k ; i++)
#define pb push_back

typedef vector<int> vi;

inline int smax(int &a, int b) { return a < b ? a = b : a; }

const int N = 1e5 + 10;

vi adj[N];

int dp[N][2], stype[N], cc[N];

void dfs(int v) {
	int pd[2][2] = {{0 , 0} , {0 , 0 }};
	for (auto e : adj[v]) {
		dfs(e);
		int pd2[2][2];
		rep(x , 0 , 2) rep(y , 0 , 2) pd2[x][y] = pd[x][y];
		rep(x , 0 , 2)
			rep(y , 0 , 2) {
				smax(pd[x][y] , pd2[x][y] + dp[e][0]);
				if (stype[e] == 0) 
					smax(pd[1][y] , pd2[x][y] + dp[e][1]);
				else if (stype[e] == 1) { 
					if (!x) smax(pd[x][1] , pd2[x][y] + dp[e][1]);
				}
				else { 
					if (!x) smax(pd[1][1] , pd2[x][y] + dp[e][1]);
				}
			}

	}

	smax(pd[0][1] , pd[0][0]);
	smax(pd[1][1] , pd[1][0]);
	dp[v][0] = max(pd[0][0] , pd[1][0]);
	dp[v][1] = max(dp[v][0] , max(pd[1][1],  cc[v] + pd[0][1]));
}

int findSample(int n,int C[],int P[],int tp[]){

	memcpy(stype , tp , n * 4);
	memcpy(cc , C , n * 4);

	rep(i , 1 , n) 
		adj[P[i]].pb(i);
	dfs(0);

	return dp[0][1];
}

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