제출 #1015356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015356		AmirAli_H1	Friend (IOI14_friend)	C++17	100 / 100	41 ms	10572 KiB

friend

// In the name of Allah

#include <bits/stdc++.h>
#include "friend.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 4;
const int oo = 1e9 + 7;

int n;
vector<pii> adj[maxn];
int A[maxn], dp[maxn][4][2];
int val[4][2];

void dfs(int v) {
	for (int R1 = 0; R1 < 4; R1++) {
		for (int R2 = 0; R2 < 2; R2++) {
			if (R2 == 0) {
				if (!(R1 & 1) && !(R1 & 2)) dp[v][R1][R2] = 0;
				else dp[v][R1][R2] = -oo;
			}
			else {
				dp[v][R1][R2] = dp[v][R1][1 - R2];
				if (!(R1 & 1) && (R1 & 2)) dp[v][R1][R2] = max(dp[v][R1][R2], A[v]);
			}
		}
	}
	for (auto f : adj[v]) {
		int u = f.F, op = f.S;
		dfs(u);
		for (int R1 = 0; R1 < 4; R1++) {
			for (int R2 = 0; R2 < 2; R2++) {
				val[R1][R2] = dp[v][R1][R2];
			}
		}
		for (int R1 = 0; R1 < 4; R1++) {
			for (int R2 = 0; R2 < 2; R2++) {
				for (int S1 = 0; S1 < 4; S1++) {
					int T1 = 0;
					if (S1 & 2) T1 = op;
					for (int S2 = 0; S2 < 2; S2++) {
						if ((R1 & 1) && (T1 & 2)) continue;
						if (R2 == 1 && (T1 & 1)) continue;
						val[R1 | T1][R2] = max(val[R1 | T1][R2], dp[v][R1][R2] + dp[u][S1][S2]);
					}
				}
			}
		}
		for (int R1 = 0; R1 < 4; R1++) {
			for (int R2 = 0; R2 < 2; R2++) {
				if (R2 == 0) dp[v][R1][R2] = 0;
				else dp[v][R1][R2] = dp[v][R1][1 - R2];
				dp[v][R1][R2] = max(dp[v][R1][R2], val[R1][R2]);
			}
		}
	}
}

int findSample(int Nx, int ax[], int px[], int opx[]) {
	n = Nx;
	for (int i = 0; i < n; i++) A[i] = ax[i];
	for (int i = 1; i < n; i++) {
		int par = px[i], op = opx[i] + 1;
		adj[par].pb(Mp(i, op));
	}
	dfs(0);
	
	int res = -oo;
	for (int R1 = 0; R1 < 4; R1++) {
		for (int R2 = 0; R2 < 2; R2++) {
			res = max(res, dp[0][R1][R2]);
		}
	}
	return res;
}

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