Submission #1025704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025704		socpite	Friend (IOI14_friend)	C++17	100 / 100	26 ms	7960 KiB

friend

#include "friend.h"
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5+5;
const int INF = 1e9+5;

int dp[maxn][2];
int W[maxn];
vector<pair<int, int>> g[maxn];

void dfs(int x){
	for(auto v: g[x])dfs(v.first);
	int sz = g[x].size();
	int tdp[2][2] = {{0, -INF}, {-INF, -INF}}, ndp[2][2] = {{-INF, -INF}, {-INF, -INF}};
	for(auto v: g[x]){
		for(int i = 0; i < 2; i++){
			for(int j = 0; j < 2; j++){
				ndp[i][j] = max(ndp[i][j], tdp[i][j] + dp[v.first][0]);
				if(v.second == 0 || i == 0)ndp[i|(v.second!=1)][j|(v.second!=0)] = max(ndp[i|(v.second!=1)][j|(v.second!=0)], tdp[i][j] + dp[v.first][1]);
			}
		}
		for(int i = 0; i < 2; i++){
			for(int j = 0; j < 2; j++){
				tdp[i][j] = ndp[i][j];
				ndp[i][j] = -INF;
			}
		}
	}
	dp[x][0] = max(tdp[1][0], tdp[0][0]);
	dp[x][1] = max(tdp[1][1], tdp[0][1]);
	dp[x][1] = max(dp[x][1], max(tdp[0][0], tdp[0][1]) + W[x]);
}

// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
	for(int i = 0; i < n; i++){
		W[i] = confidence[i];
		if(i){
			g[host[i]].push_back({i, protocol[i]});
		}
	}
	dfs(0);
	return max(dp[0][0], dp[0][1]);
}

Compilation message (stderr)

friend.cpp: In function 'void dfs(int)':
friend.cpp:14:6: warning: unused variable 'sz' [-Wunused-variable]
   14 |  int sz = g[x].size();
      |      ^~

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