oj.uz

Submission #114409

# Submission time Handle Problem Language Result Execution time Memory
114409 2019-06-01T08:46:03 Z E869120 Friend (IOI14_friend) C++14
46 / 100
 38 ms 11516 KB 
#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;
}

Compilation message

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9700 KB Output is correct
2 Correct 10 ms 9820 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 10 ms 9740 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9772 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 10 ms 9728 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 10 ms 9700 KB Output is correct
11 Correct 11 ms 9728 KB Output is correct
12 Correct 10 ms 9728 KB Output is correct
13 Correct 10 ms 9728 KB Output is correct
14 Correct 10 ms 9728 KB Output is correct
15 Correct 10 ms 9728 KB Output is correct
16 Correct 10 ms 9700 KB Output is correct
17 Correct 11 ms 9728 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9828 KB Output is correct
2 Correct 10 ms 9776 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 10 ms 9772 KB Output is correct
5 Correct 10 ms 9856 KB Output is correct
6 Correct 10 ms 9828 KB Output is correct
7 Correct 10 ms 9828 KB Output is correct
8 Correct 10 ms 9828 KB Output is correct
9 Correct 11 ms 9832 KB Output is correct
10 Correct 10 ms 9856 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9772 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9776 KB Output is correct
4 Correct 11 ms 9796 KB Output is correct
5 Correct 11 ms 9792 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 10 ms 9772 KB Output is correct
8 Correct 10 ms 9728 KB Output is correct
9 Correct 10 ms 9772 KB Output is correct
10 Correct 10 ms 9728 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9776 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 11 ms 10000 KB Output is correct
6 Correct 10 ms 9856 KB Output is correct
7 Correct 9 ms 9728 KB Output is correct
8 Correct 10 ms 9856 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 10 ms 9828 KB Output is correct
11 Correct 10 ms 9756 KB Output is correct
12 Correct 11 ms 9828 KB Output is correct
13 Correct 11 ms 9940 KB Output is correct
14 Correct 9 ms 9856 KB Output is correct
15 Correct 11 ms 9916 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9792 KB Output is correct
2 Correct 10 ms 9736 KB Output is correct
3 Correct 9 ms 9700 KB Output is correct
4 Correct 9 ms 9680 KB Output is correct
5 Correct 9 ms 9772 KB Output is correct
6 Correct 10 ms 9784 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 10 ms 9812 KB Output is correct
9 Correct 12 ms 9984 KB Output is correct
10 Correct 11 ms 9800 KB Output is correct
11 Incorrect 10 ms 9728 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 9 ms 9764 KB Output is correct
7 Correct 10 ms 9852 KB Output is correct
8 Correct 10 ms 9728 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 9 ms 9728 KB Output is correct
11 Correct 9 ms 9728 KB Output is correct
12 Incorrect 38 ms 11516 KB Output isn't correct
13 Halted 0 ms 0 KB -