제출 #398062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398062		prvocislo	Friend (IOI14_friend)	C++17	27 / 100	1 ms	460 KiB

friend

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
typedef long long ll;
using namespace std;

const int maxn = 1e5 + 79;
int dp[maxn][2]; // dp[vr][isiel nas kamos?]
int dfs(int u, int fr, const vector<vector<pair<int, int> > >& g, int c[])
{
	if (dp[u][fr] != -1) return dp[u][fr];
	int go = c[u], dont = 0;
	for (const pair<int, int>& i : g[u])
	{
		int fr2 = (i.second ? fr : 0), p2 = (i.second != 1);
		go += dfs(i.first, (fr2 | p2), g, c);
		dont += dfs(i.first, fr2, g, c);
	}
	return dp[u][fr] = max(dont, go * (1 - fr));
}
int findSample(int n, int c[], int h[], int pr[])
{
	vector<vector<pair<int, int> > > g(n);
	for (int i = 1; i < n; i++)
		g[h[i]].push_back({ i, pr[i] });
	for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++) dp[i][j] = -1;
	int ans = dfs(0, 0, g, c);
	//for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++) cout << dp[i][j] << " \n"[j == 1];
	return ans;
}

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