oj.uz

Submission #764041

# Submission time Handle Problem Language Result Execution time Memory
764041 2023-06-23T06:07:31 Z SanguineChameleon Friend (IOI14_friend) C++17
46 / 100
 34 ms 7972 KB 
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 20;
vector<pair<int, int>> ch[maxn];
int a[maxn];
int dp[maxn][2];

void dfs(int u) {
	for (auto e: ch[u]) {
		int v = e.first;
		dfs(v);
	}
	int sum = a[u];
	for (auto e: ch[u]) {
		int v = e.first;
		int op = e.second;
		if (op == 1) {
			sum += max(dp[v][0], dp[v][1]);
		}
		else {
			sum += dp[v][0];
		}
	}
	dp[u][1] = max(dp[u][1], sum);
	int sz = ch[u].size();
	vector<int> pref(sz);
	vector<int> suf(sz);
	sum = 0;
	for (int i = sz - 1; i >= 0; i--) {
		pair<int, int> e = ch[u][i];
		int v = e.first;
		int op = e.second;
		if (op == 0) {
			sum += max(dp[v][0], dp[v][1]);
		}
		suf[i] = sum;
	}
	sum = 0;
	for (int i = 0; i < sz; i++) {
		pair<int, int> e = ch[u][i];
		int v = e.first;
		int op = e.second;
		if (op == 1) {
			sum += dp[v][0];
		}
		else {
			pref[i] = sum + (op == 0 ? max(dp[v][0], dp[v][1]) : dp[v][0]);
			dp[u][0] = max(dp[u][0], pref[i] + (i < sz - 1 ? suf[i + 1] : 0));
		}
	}
	dp[u][0] = max(dp[u][0], sum);
	sum = 0;
	for (int i = 0; i < sz; i++) {
		pair<int, int> e = ch[u][i];
		int v = e.first;
		int op = e.second;
		if (op == 1) {
			sum += max(dp[v][0], dp[v][1]);
		}
		else {
			pref[i] = sum + max(dp[v][0], dp[v][1]);
			dp[u][1] = max(dp[u][1], pref[i] + (i < sz - 1 ? suf[i + 1] : 0));
		}
	}
	dp[u][1] = max(dp[u][1], sum);
}

int findSample(int n, int confidence[], int host[], int protocol[]){
	for (int i = 0; i < n; i++) {
		a[i] = confidence[i];
	}
	for (int v = 1; v < n; v++) {
		ch[host[v]].emplace_back(v, protocol[v]);
	}
	for (int i = 0; i < n; i++) {
		sort(ch[i].begin(), ch[i].end());
	}
	dfs(0);
	return max(dp[0][0], dp[0][1]);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2660 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2668 KB Output is correct
9 Correct 2 ms 2664 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 1 ms 2660 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Correct 2 ms 2664 KB Output is correct
17 Correct 1 ms 2644 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2672 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2792 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2768 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2672 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2672 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 1 ms 2772 KB Output is correct
10 Correct 2 ms 2792 KB Output is correct
11 Incorrect 2 ms 2644 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2564 KB Output is correct
3 Correct 1 ms 2664 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2660 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 1 ms 2664 KB Output is correct
11 Correct 1 ms 2656 KB Output is correct
12 Incorrect 34 ms 7972 KB Output isn't correct
13 Halted 0 ms 0 KB -