oj.uz

Submission #70387

# Submission time Handle Problem Language Result Execution time Memory
70387 2018-08-22T18:56:12 Z Abelyan Friend (IOI14_friend) C++17
100 / 100
 45 ms 7084 KB 
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;

const int N=100006;
int choose[N],notChoose[N];

int findSample(int n,int value[],int host[],int protocol[]){
	for (int i=0;i<n;i++){
		choose[i]=value[i];
	}
	for (int i=n-1;i>0;i--){
		int v=host[i];
		if (protocol[i]==0){
			choose[v]+=notChoose[i];
			notChoose[v]+=max(notChoose[i],choose[i]);
		}
		else if (protocol[i]==1){
			choose[v]=max(choose[v]+choose[i],max(choose[v]+notChoose[i],choose[i]+notChoose[v]));
			notChoose[v]+=notChoose[i];
		}
		else{
			choose[v]=max(choose[v]+notChoose[i],choose[i]+notChoose[v]);
			notChoose[v]+=notChoose[i];
		}
		//cout<<choose[v]<<" "<<notChoose[v]<<endl;
	}
	return max(choose[0],notChoose[0]);
}
/*
#define __MAXSIZE__ 100002

// Confidence
int confidence[__MAXSIZE__];

// Host
int host[__MAXSIZE__];

// Protocol
int protocol[__MAXSIZE__];

// Main
int main(void)
{
	int n,i;

	// Number of people
	assert(scanf("%d",&n)==1);
	
	// Confidence
	for(i=0;i<n;i++)
		assert(scanf("%d",&confidence[i])==1);
	
	// Host and Protocol
	for(i=1;i<n;i++)
		assert(scanf("%d %d",&host[i],&protocol[i])==2);
	
	// Answer
	printf("%d\n",findSample(n,confidence,host,protocol));
	return 0;
}
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 3 ms 476 KB Output is correct
4 Correct 3 ms 476 KB Output is correct
5 Correct 3 ms 572 KB Output is correct
6 Correct 3 ms 572 KB Output is correct
7 Correct 2 ms 572 KB Output is correct
8 Correct 3 ms 572 KB Output is correct
9 Correct 2 ms 688 KB Output is correct
10 Correct 2 ms 688 KB Output is correct
11 Correct 2 ms 688 KB Output is correct
12 Correct 2 ms 688 KB Output is correct
13 Correct 2 ms 796 KB Output is correct
14 Correct 2 ms 796 KB Output is correct
15 Correct 3 ms 796 KB Output is correct
16 Correct 3 ms 820 KB Output is correct
17 Correct 3 ms 820 KB Output is correct

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 820 KB Output is correct
2 Correct 4 ms 820 KB Output is correct
3 Correct 3 ms 820 KB Output is correct
4 Correct 4 ms 820 KB Output is correct
5 Correct 3 ms 824 KB Output is correct
6 Correct 2 ms 836 KB Output is correct
7 Correct 2 ms 840 KB Output is correct
8 Correct 3 ms 844 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 4 ms 856 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 872 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Correct 2 ms 880 KB Output is correct
4 Correct 2 ms 884 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 2 ms 912 KB Output is correct
8 Correct 4 ms 916 KB Output is correct
9 Correct 3 ms 932 KB Output is correct
10 Correct 3 ms 932 KB Output is correct
11 Correct 3 ms 936 KB Output is correct
12 Correct 3 ms 944 KB Output is correct
13 Correct 3 ms 956 KB Output is correct
14 Correct 2 ms 968 KB Output is correct
15 Correct 3 ms 976 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 984 KB Output is correct
2 Correct 3 ms 988 KB Output is correct
3 Correct 3 ms 992 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 3 ms 1128 KB Output is correct
10 Correct 4 ms 1128 KB Output is correct
11 Correct 3 ms 1128 KB Output is correct
12 Correct 3 ms 1128 KB Output is correct
13 Correct 3 ms 1128 KB Output is correct
14 Correct 3 ms 1128 KB Output is correct
15 Correct 3 ms 1128 KB Output is correct
16 Correct 2 ms 1128 KB Output is correct
17 Correct 3 ms 1128 KB Output is correct
18 Correct 3 ms 1128 KB Output is correct
19 Correct 2 ms 1128 KB Output is correct
20 Correct 2 ms 1176 KB Output is correct
21 Correct 5 ms 1176 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1176 KB Output is correct
2 Correct 2 ms 1176 KB Output is correct
3 Correct 2 ms 1176 KB Output is correct
4 Correct 2 ms 1176 KB Output is correct
5 Correct 3 ms 1176 KB Output is correct
6 Correct 2 ms 1176 KB Output is correct
7 Correct 3 ms 1176 KB Output is correct
8 Correct 3 ms 1176 KB Output is correct
9 Correct 2 ms 1232 KB Output is correct
10 Correct 2 ms 1232 KB Output is correct
11 Correct 3 ms 1232 KB Output is correct
12 Correct 45 ms 4200 KB Output is correct
13 Correct 22 ms 4200 KB Output is correct
14 Correct 40 ms 5856 KB Output is correct
15 Correct 39 ms 7084 KB Output is correct