제출 #1225966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225966		ByeWorld	Friend (IOI14_friend)	C++20	100 / 100	16 ms	3908 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
// #pragma GCC optimize("O3")
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 1e5+10;
const int SQRT = 450;
const int INF = 2e9;
const int LOG = 20;
void chmn(int &a, int b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }

int n, a[MAXN];
int par[MAXN], ty[MAXN];
int dp[MAXN][3];

int findSample(int N,int confidence[],int host[],int protocol[]){
	n = N;
	for(int i=1; i<=n; i++){
		a[i] = confidence[i-1];
		dp[i][1] = a[i];
	}
	for(int i=1; i<n; i++){
		par[i+1] = host[i]+1; ty[i+1] = protocol[i];
	}
	for(int i=n; i>=2; i--){
		int up = par[i];
		int pp = dp[par[i]][1], qq = dp[par[i]][0];
		int p = dp[i][1], q = dp[i][0];

		if(ty[i]==0){ //child
			dp[up][1] = pp+q;
			dp[up][0] = qq + max(p, q);

		} else if(ty[i]==1){ // friend is friend
			dp[up][1] = max(pp+p, max(pp+q, qq+p));
			dp[up][0] = qq + q;
			
		} else {
			dp[up][1] = max(pp+q, qq+p);
			dp[up][0] = qq + q;
		}
	}
	return max(dp[1][1], dp[1][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