제출 #114409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114409		E869120	친구 (IOI14_friend)	C++14	46 / 100	38 ms	11516 KiB

friend

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

// ----------------------- 答えを求める関数 --------------------------

int N, A[100009], ty[100009], B[100009], col[100009], dp[100009][2], toku[100009];
vector<int>X[100009], E[100009]; int parcol[100009], par[100009], lim[100009];

vector<pair<int, int>>D[100009][2];

void dfs(int pos) {
	for (int i = 0; i < (int)X[pos].size(); i++) dfs(X[pos][i]);
	
	// 0 : 全部白　1 : 一個以上黒
	for (int i = 0; i <= E[pos].size(); i++) { D[i][0].clear(); D[i][1].clear(); }
	
	for (int i = 0; i < (int)X[pos].size(); i++) dp[pos][0] += max(dp[X[pos][i]][0], dp[X[pos][i]][1]);
	int S = 0; for (int i = 0; i < (int)X[pos].size(); i++) S += dp[X[pos][i]][0];
	
	map<int, int>Map; for (int i = 0; i < (int)E[pos].size(); i++) Map[E[pos][i]] = i;
	for (int i = 0; i < (int)X[pos].size(); i++) {
		int EE = Map[par[X[pos][i]]];
		D[EE + 1][0].push_back(make_pair(EE, X[pos][i]));
		D[lim[X[pos][i]]][1].push_back(make_pair(EE, X[pos][i]));
		//cout << pos << " " << EE << " " << lim[X[pos][i]] << endl;
	}
	
	int SR = 0, maxn = 0; for (int i = 0; i < (int)X[pos].size(); i++) SR += toku[X[pos][i]];
	maxn = SR; vector<int> cnt(E[pos].size(), 0);
	for (int i = 1; i <= (int)E[pos].size(); i++) {
		SR += A[E[pos][i - 1]];
		for (pair<int, int> t : D[i][0]) {
			int V1 = cnt[t.first], V2 = cnt[t.first] + toku[t.second]; V1 -= A[E[pos][t.first]]; V2 -= A[E[pos][t.first]];
			cnt[t.first] += toku[t.second]; SR -= toku[t.second];
			SR += max(V2, 0) - max(V1, 0);
		}
		maxn = max(maxn, SR);
		for (pair<int, int> t : D[i][1]) {
			int V1 = cnt[t.first], V2 = cnt[t.first] - toku[t.second]; V1 -= A[E[pos][t.first]]; V2 -= A[E[pos][t.first]];
			cnt[t.first] -= toku[t.second];
			SR += max(V2, 0) - max(V1, 0);
		}
	}
	dp[pos][1] = S + maxn;
	toku[pos] = max(dp[pos][1], dp[pos][0]) - dp[pos][0];
}

int solve() {
	E[0].push_back(0);
	for (int i = 1; i < N; i++) {
		if (ty[i] == 0) {
			col[i] = i;
			parcol[i] = col[B[i]];
			par[i] = B[i];
			lim[i] = E[parcol[i]].size();
			X[parcol[i]].push_back(i);
			E[col[i]].push_back(i);
		}
		if (ty[i] == 1) {
			col[i] = col[B[i]];
			E[col[i]].push_back(i);
		}
	}
	/*for (int i = 0; i < N; i++) {
		printf("% 3d: col =% 3d, parcol =% 3d, par =% 3d, lim =% 3d, ", i, col[i], parcol[i], par[i], lim[i]);
		printf("X = {"); for (int j = 0; j < X[i].size(); j++) { if (j) printf(","); printf("% 3d", X[i][j]); } printf("}, ");
		printf("E = {"); for (int j = 0; j < E[i].size(); j++) { if (j) printf(","); printf("% 3d", E[i][j]); } printf("}\n");
	}*/
	dfs(0);
	/*cout << "--- DP TABLE ---" << endl;
	for (int i = 0; i < N; i++) {
		if (dp[i][0] == 0 && dp[i][1] == 0) continue;
		printf("% 3d: % 3d, % 3d\n", i, dp[i][0], dp[i][1]);
	}*/
	return max(dp[0][0], dp[0][1]);
}

// --------------------------- 場合分け -----------------------------

int findSample(int n,int confidence[],int host[],int protocol[]){
	int bit = 0;
	for (int i = 1; i <= n - 1; i++) bit |= (1 << protocol[i]);
	
	if (bit <= 3) {
		N = n;
		for (int i = 0; i < N; i++) A[i] = confidence[i];
		for (int i = 1; i < N; i++) { ty[i] = protocol[i]; B[i] = host[i]; }
		return solve();
	}
	if (bit == 4) {
		// Subtask 3.
		int sum = 0; for (int i = 0; i < n; i++) sum = max(sum, confidence[i]);
		return sum;
	}
	if (n <= 10) {
		// Subtask 1.
		vector<int>G[10];
		for (int i = 1; i <= n - 1; i++) {
			if (protocol[i] == 0 || protocol[i] == 2) {
				G[host[i]].push_back(i);
				G[i].push_back(host[i]);
			}
			if (protocol[i] == 1 || protocol[i] == 2) {
				for (int pos : G[host[i]]) {
					if (pos == i) continue;
					G[pos].push_back(i);
					G[i].push_back(pos);
				}
			}
		}
		int ans = 0;
		for (int i = 0; i < (1 << n); i++) {
			bool flag = false; int sum = 0;
			int bit[10]; for (int j = 0; j < n; j++) { bit[j] = (i / (1 << j)) % 2; sum += bit[j] * confidence[j]; }
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < G[j].size(); k++) { if (bit[j] == 1 && bit[G[j][k]] == 1) flag = true; }
			}
			if (flag == false) ans = max(ans, sum);
		}
		return ans;
	}
	return -1;
}

컴파일 시 표준 에러 (stderr) 메시지

friend.cpp: In function 'void dfs(int)':
friend.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= E[pos].size(); i++) { D[i][0].clear(); D[i][1].clear(); }
                  ~~^~~~~~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:117:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int k = 0; k < G[j].size(); k++) { if (bit[j] == 1 && bit[G[j][k]] == 1) flag = true; }
                     ~~^~~~~~~~~~~~~

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