Submission #1015198

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1015198	2024-07-06T07:22:24 Z	parsadox2	Friend (IOI14_friend)	C++17	19 / 100	1 ms	4740 KB

friend

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

using namespace std;

const int N = 1e5 + 10;
int n , ar[N] , dp[N][2];
bool par[N] , prv[N];
vector <int> adj[N];

void Dfs(int v)
{
	for(auto u : adj[v])
		Dfs(u);
	if(adj[v].empty())
	{
		dp[v][1] = ar[v];
		//cout << v << " : " << dp[v][0] << " " << dp[v][1] << endl;
		return;
	}
	int tmp[2];
	tmp[0] = tmp[1] = 0;
	for(auto u : adj[v])
	{
		if(prv[u])
			tmp[1] = max(tmp[1] + dp[u][0] , tmp[0] + dp[u][1]);
		else
			tmp[1] += dp[u][1];
		tmp[0] += dp[u][0];
	}
	dp[v][0] = tmp[1];
	tmp[0] = tmp[1] = ar[v];
	for(auto u : adj[v])
	{
		if(par[u])
			tmp[1] += dp[u][0];
		else if(prv[u])
			tmp[1] = max(tmp[1] + dp[u][0] , tmp[0] + dp[u][1]);
		else
			tmp[1] += dp[u][1];
		tmp[0] += dp[u][0];
	}
	dp[v][1] = max(dp[v][0] , tmp[1]);
	//cout << v << " : " << dp[v][0] << " " << dp[v][1] << endl;
}

int findSample(int nn,int confidence[],int host[],int protocol[]){
	n = nn;
	for(int i = 0 ; i < n ; i++)
		ar[i] = confidence[i];
	for(int i = 1 ; i < n ; i++)
	{
		adj[host[i]].push_back(i);
		if(protocol[i] == 0)
			par[i] = true;
		else if(protocol[i] == 1)
			prv[i] = true;
		else
		{
			par[i] = true;
			prv[i] = true;
		}
	}
	Dfs(0);
	return dp[0][1];
}

Subtask #1

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4696 KB	Output is correct
2	Correct	1 ms	4696 KB	Output is correct
3	Correct	1 ms	4700 KB	Output is correct
4	Correct	1 ms	4700 KB	Output is correct
5	Correct	1 ms	4700 KB	Output is correct
6	Correct	1 ms	4700 KB	Output is correct
7	Incorrect	1 ms	4700 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	4700 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	4700 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4696 KB	Output is correct
2	Correct	1 ms	4696 KB	Output is correct
3	Correct	1 ms	4700 KB	Output is correct
4	Correct	1 ms	4700 KB	Output is correct
5	Correct	1 ms	4700 KB	Output is correct
6	Correct	1 ms	4696 KB	Output is correct
7	Correct	1 ms	4700 KB	Output is correct
8	Correct	1 ms	4740 KB	Output is correct
9	Correct	1 ms	4700 KB	Output is correct
10	Correct	1 ms	4700 KB	Output is correct
11	Correct	1 ms	4700 KB	Output is correct
12	Correct	1 ms	4700 KB	Output is correct
13	Correct	1 ms	4700 KB	Output is correct
14	Correct	1 ms	4700 KB	Output is correct
15	Correct	1 ms	4700 KB	Output is correct

Subtask #5

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4700 KB	Output is correct
2	Correct	1 ms	4700 KB	Output is correct
3	Correct	1 ms	4700 KB	Output is correct
4	Incorrect	1 ms	4696 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #6

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4700 KB	Output is correct
2	Correct	1 ms	4724 KB	Output is correct
3	Correct	1 ms	4700 KB	Output is correct
4	Correct	1 ms	4700 KB	Output is correct
5	Correct	1 ms	4700 KB	Output is correct
6	Correct	1 ms	4700 KB	Output is correct
7	Correct	1 ms	4700 KB	Output is correct
8	Correct	1 ms	4700 KB	Output is correct
9	Correct	1 ms	4700 KB	Output is correct
10	Correct	1 ms	4700 KB	Output is correct
11	Incorrect	1 ms	4696 KB	Output isn't correct
12	Halted	0 ms	0 KB	-