Submission #285706

#	Time	Username	Problem	Language	Result	Execution time	Memory
285706		amoo_safar	Friend (IOI14_friend)	C++17	100 / 100	68 ms	8312 KiB

friend

#include "friend.h"

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

// Find out best sample
const int N = 1e5 + 10;
const int Inf = 1e9;

int ty[N], C[N];
vector<int> G[N];

int dp[N][4];
int pd[N], tmp[4];

void DFS(int u){
	for(auto adj : G[u])
		DFS(adj);
	fill(pd, pd + 4, 0);
	reverse(G[u].begin(), G[u].end());
	for(auto adj : G[u])
	{
		fill(tmp, tmp + 4, 0);
		for(int mkA = 0; mkA < 4; mkA ++)
		{
			for(int mkD = 0; mkD < 4; mkD ++)
			{
				if(((mkD & 2) == 2) && ((mkA & 1) == 1)) continue;
				tmp[mkA | mkD] = max(tmp[mkA | mkD], dp[adj][mkA] + pd[mkD]);
			}
		}
		for(int i = 0; i < 4; i++) pd[i] = tmp[i];
	}
	//if(u == 0) cerr << "#### " << pd[2] << '\n';
	for(int pi = 0; pi < 2; pi ++)
	{
		for(int mkD = 0; mkD < 4; mkD ++)
		{
			if(((mkD & 1) == 1) && (pi == 1)) continue;
			int fr = 0, frfr = 0;
			if(mkD & 2){
				if(ty[u] & 1) fr = 1;
				if(ty[u] & 2) frfr = 1;
			}
			if(pi == 1 && ((ty[u] & 1) == 1)) fr = 1;
			if(pi == 1 && ((ty[u] & 2) == 2)) frfr = 1;

			dp[u][fr + 2*frfr] = max(dp[u][fr + 2*frfr], pd[mkD] + pi * C[u]);
		}
	}
}

int findSample(int n, int val[], int par[], int type[]){
	for(int i = 1; i < n; i++)
		G[par[i]].pb(i);
	for(int i = 1; i < n; i++) ty[i] = type[i] + 1; 
	for(int i = 0; i < n; i++) C[i] = val[i];
	DFS(0);
	//for(int i = 0; i < 2; i++) for(int j = 0; j < 4; j++) cerr << "! " << i << ' ' << j << " -> " << dp[i][j] << '\n';
	return *max_element(dp[0], dp[0] + 4);
}

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