oj.uz

Submission #404200

# Submission time Handle Problem Language Result Execution time Memory
404200 2021-05-13T23:55:10 Z Kenzo_1114 Friend (IOI14_friend) C++17
46 / 100
 32 ms 5324 KB 
#include<bits/stdc++.h>
#include"friend.h"
using namespace std;
const int MAXN = 100010;

int n, c[MAXN], h[MAXN], p[MAXN];

/*
	0 : IAmYourFriend
	1 : MyFriendsAreYourFriends
	2 : WeAreYourFriends
*/

int Bkt = 0;
bool mark[20], adj[20][20];

void bkt(int id)
{
	if(id == n)
	{
		bool ok = true;
		for(int i = 0; i < n; i++)
			for(int j = i + 1; j < n; j++)
				if(mark[i] && mark[j] && adj[i][j])
					ok = false;
		if(!ok)	return;

		int sum = 0;
		for(int i = 0; i < n; i++)
			if(mark[i])	sum += c[i];
		
		Bkt = max(Bkt, sum);
		return;
	}

	mark[id] = true;
	bkt(id + 1);
	mark[id] = false;
	bkt(id + 1);
}

int task1()
{
	for(int i = 1; i < n; i++)
	{
		int a = h[i];
		int b = i;

		if(p[i] == 0 || p[i] == 2)	adj[a][b] = adj[b][a] = true;
		if(p[i] > 0)	
			for(int j = 0; j < n; j++)
				if(a != j && adj[a][j]) 
					adj[b][j] = adj[j][b] = true;
	}

	bkt(0);
	return Bkt;
}

int task2()
{
	int ans = 0;
	for(int i = 0; i < n; i++)
	{
		if(i && p[i] != 1)	return 0;
		ans += c[i];
	}

	return ans;
}

int task3()
{
	int ans = 0;
	for(int i = 0; i < n; i++)
	{
		if(i && p[i] != 2)	return 0;
		ans = max(ans, c[i]);
	}

	return ans;
}
	
int dp[2][MAXN];
vector<int> graph[MAXN];

int dfs4(int v, int p)
{
	dp[1][v] = c[v];

	for(int i = 0; i < (int) graph[v].size(); i++)
	{
		int u = graph[v][i];
		if(u == p)	continue;

		dp[0][v] += dfs4(u, v);
		dp[1][v] += dp[0][u];
	}

	return max(dp[0][v], dp[1][v]);
}

int task4()
{
	for(int i = 1; i < n; i++)
		if(p[i] != 0)	return 0;

	for(int i = 1; i < n; i++)
	{
		int a = h[i];
		int b = i;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	return dfs4(0, 0);
}

int color[MAXN];

int task5()
{
	for(int i = 1; i < n; i++)
	{
		int a = h[i];
		int b = i;

		if(p[i] == 0)	color[b] = !color[a];
		else	color[b] = color[a];	
	}	

	int ans[2] = {0, 0};
	for(int i = 0; i < n; i++)
		ans[color[i]] += c[i];

	return max(ans[0], ans[1]);
}

int findSample(int N, int Confidence[], int Host[], int Protocol[])
{
	n = N;
	for(int i = 0; i < N; i++)	c[i] = Confidence[i];
	for(int i = 0; i < N; i++)	h[i] = Host[i];
	for(int i = 0; i < N; i++)	p[i] = Protocol[i];

	if(n <= 10)	return task1();

	int ans = task2();
	if(ans)	return ans;

	ans = task3();
	if(ans)	return ans;
	
	ans = task4();
	if(ans)	return ans;

	return task5();
}

Subtask #1
11.0 / 11.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2572 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct

Subtask #4
19.0 / 19.0

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

Subtask #5
0 / 23.0

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

Subtask #6
0 / 31.0

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