oj.uz

답안 #113464

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
113464 2019-05-25T16:55:46 Z Beautiful_Times 친구 (IOI14_friend) C++14
27 / 100
 7 ms 3584 KB 
#include <bits/stdc++.h>
#include <queue> 
#include <vector>
#include <friend.h>
using namespace std;

vector<int> child[100001];
int cod[6];
int ho[6];
int pro[6];
int dpp[100001][2];
int conn[100001];
int dp(int node, bool inc)
{
	int temp;
	if(inc)
		temp = 1;
	else
		temp = 0;
	if(dpp[node][temp] != -1)
		return dpp[node][temp];

	if(inc == true)
	{
		int total = conn[node];
		for(int x = child[node].size()-1;x>=0;x-=2)
		{
			int nn = child[node].at(x-1);
			int proc = child[node].at(x);
			if(proc == 1)
				total += max(dp(nn,true),dp(nn,false));
			else
				total += dp(nn,false);
		}
		dpp[node][temp] = total;
	}
	else
	{	
		int current = 0;
		int include2 = 0;
		int include1 = 0;
		for(int x = child[node].size()-1;x>=0;x-=2)
		{
			int nn = child[node].at(x-1);
			int proc = child[node].at(x);
			if(proc == 0)
			{
				int diff = dp(nn,true) - dp(nn,false);
				if(diff <= 0)
					current += dp(nn,false);
				else
				{
					if(include1 + diff > include2)
					{
						current += include1 + dp(nn,true);
						current -= include2;
						include1 = 0;
						include2 = 0;
					}
					else
					{
						include1 += diff;
						current += dp(nn,false);
					}
				}					
			}
			else
			{
				int diff = dp(nn,true) - dp(nn,false);
				if(diff < 0)
					current += dp(nn,false);
				else
				{
					current += dp(nn,true);
					include2 += diff;
				}
			}
		}
		dpp[node][temp] = current;
	}
	return dpp[node][temp];
	
}

int findSample(int n, int confidence[], int host[], int protocol[])
{
	for(int x = 1;x<n;x++)
	{
		child[host[x]].push_back(x);
		child[host[x]].push_back(protocol[x]);

	}
	for(int x = 0;x<100001;x++)
	{
		dpp[x][0] = -1;
		dpp[x][1] = -1;
	}	
	for(int x = 0;x<n;x++)
	{
		conn[x] = confidence[x];
	}
	return max(dp(0,false),dp(0,true));
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3584 KB Output is correct
2 Correct 5 ms 3456 KB Output is correct
3 Correct 7 ms 3456 KB Output is correct
4 Correct 4 ms 3456 KB Output is correct
5 Correct 5 ms 3456 KB Output is correct
6 Correct 5 ms 3524 KB Output is correct
7 Incorrect 5 ms 3456 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 5 ms 3456 KB Output is correct
3 Correct 5 ms 3456 KB Output is correct
4 Correct 5 ms 3584 KB Output is correct
5 Correct 5 ms 3584 KB Output is correct
6 Correct 5 ms 3456 KB Output is correct
7 Correct 5 ms 3456 KB Output is correct
8 Correct 5 ms 3456 KB Output is correct
9 Correct 5 ms 3584 KB Output is correct
10 Correct 5 ms 3456 KB Output is correct

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 5 ms 3456 KB Output is correct
3 Correct 5 ms 3456 KB Output is correct
4 Correct 5 ms 3456 KB Output is correct
5 Correct 6 ms 3584 KB Output is correct
6 Correct 5 ms 3456 KB Output is correct
7 Correct 4 ms 3456 KB Output is correct
8 Correct 4 ms 3584 KB Output is correct
9 Correct 5 ms 3456 KB Output is correct
10 Correct 5 ms 3456 KB Output is correct
11 Correct 5 ms 3456 KB Output is correct
12 Correct 5 ms 3456 KB Output is correct
13 Correct 5 ms 3584 KB Output is correct
14 Correct 5 ms 3456 KB Output is correct
15 Correct 5 ms 3584 KB Output is correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 5 ms 3456 KB Output is correct
3 Correct 4 ms 3456 KB Output is correct
4 Correct 4 ms 3456 KB Output is correct
5 Correct 4 ms 3456 KB Output is correct
6 Correct 4 ms 3456 KB Output is correct
7 Correct 5 ms 3456 KB Output is correct
8 Correct 4 ms 3456 KB Output is correct
9 Correct 5 ms 3584 KB Output is correct
10 Correct 5 ms 3584 KB Output is correct
11 Incorrect 5 ms 3456 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 5 ms 3456 KB Output is correct
3 Correct 4 ms 3456 KB Output is correct
4 Correct 4 ms 3536 KB Output is correct
5 Correct 5 ms 3456 KB Output is correct
6 Correct 4 ms 3456 KB Output is correct
7 Correct 5 ms 3456 KB Output is correct
8 Correct 5 ms 3456 KB Output is correct
9 Correct 4 ms 3584 KB Output is correct
10 Correct 4 ms 3456 KB Output is correct
11 Incorrect 5 ms 3456 KB Output isn't correct
12 Halted 0 ms 0 KB -