Submission #586529

#	Time	Username	Problem	Language	Result	Execution time	Memory
586529		SeDunion	Friend (IOI14_friend)	C++17	100 / 100	27 ms	2236 KiB

friend

#include "friend.h"
#include<iostream>
#include<assert.h>
#include<vector>

using namespace std;

const int N = 1e5 + 123;

int p[N], q[N];

int findSample(int n,int confidence[],int host[],int protocol[]){
	for (int i = 0 ; i < n ; ++ i) {
		p[i] = confidence[i];
		q[i] = 0;
	}
	for (int y = n - 1 ; y > 0 ; -- y) {
		int x = host[y];
		if (protocol[y] == 0) {
			int np = p[x] + q[y];
			int nq = max(q[x] + p[y], q[x] + q[y]);
			p[x] = np, q[x] = nq;
		} else if (protocol[y] == 1) {
			int np = max(max(p[x] + p[y], p[x] + q[y]), q[x] + p[y]);
			int nq = q[x] + q[y];
			p[x] = np, q[x] = nq;
		} else {
			int np = max(p[x] + q[y], q[x] + p[y]);
			int nq = q[x] + q[y];
			p[x] = np, q[x] = nq;
		}
	}
	return max(p[0], q[0]);
}

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