oj.uz

답안 #774094

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
774094 2023-07-05T12:00:38 Z loctildore 친구 (IOI14_friend) C++14
27 / 100
 26 ms 3144 KB 
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
// trans rights
#define ll long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
#define MOD 1000000009

vector<int> grph[1069];
int con[1069];
bool done[1069];

int dp[1069][2];

bool col[1069];

int ans = 0;

int dfs1(int x) {
	if (done[x]) return 0;
	done[x] = true;
	int rtn = con[x];
	for (auto i : grph[x]) rtn = max(rtn, dfs1(i));
	return rtn;
}

int dfs2(int x, int lst, int chs = 1) {
	if (dp[x][chs]) return dp[x][chs]; //only 0 at the edges anyway
	if (!chs) {
		for (auto i : grph[x]) if (i != lst) dp[x][chs] += dfs2(i, x, 1);
		return dp[x][chs];
	}
	dp[x][chs] += con[x];
	for (auto i : grph[x]) if (i != lst) dp[x][chs] += dfs2(i, x, 0);
	return dp[x][chs] = max(dp[x][chs], dp[x][0]);
}

int v[2];
void dfs3(int x, int lst = -1) {
	if (done[x]) return;
	done[x] = true;
	v[col[x]]++;
	for (auto i : grph[x]) if (i != lst) dfs3(i, x);
}

int findSample(int n, int confidence[], int host[], int protocol[]){
	if (n <= 10) {
		for (int i = 1; i < n; i++) {
			if (protocol[i] != 0) {
				for (auto t : grph[host[i]]) {
					grph[i].push_back(t);
					grph[t].push_back(i);
				}
			}
			if (protocol[i] != 1) {
				grph[i].push_back(host[i]);
				grph[host[i]].push_back(i);
			}
		}
		for (int bst = 0; bst < (1 << n); bst++) {
			int cur = 0;
			bool flag = true;
			for (int i = 0; i < n; i++) {
				if (!(bst & (1 << i))) continue;
				for (auto j : grph[i]) if (bst & (1 << j)) {
					flag = false;
				}
				cur += confidence[i];
			}
			if (flag) ans = max(ans, cur);
		}
		return ans;
	}

	bool flag = true;
	for (int i = 1; i < n; i++) if (protocol[i] != 1) flag = false;
	if (flag) {
		for (int i = 0; i < n; i++) {
			ans += confidence[i];
		}
		return ans;
	}

	for (int i = 0; i < n; i++) con[i] = confidence[i];
	for (int i = 1; i < n; i++) grph[i].push_back(host[i]);
	for (int i = 1; i < n; i++) grph[host[i]].push_back(i);

	flag = true;
	for (int i = 1; i < n; i++) if (protocol[i] != 2) flag = false;
	if (flag) {
		for (int i = 0; i < n; i++) {
			if (!dp[i][1]) ans += dfs1(i);
		}
		return ans;
	}

	flag = true;
	for (int i = 1; i < n; i++) if (protocol[i] != 0) flag = false;
	if (flag) {
		for (int i = 0; i < n; i++) {
			ans += dfs2(i, -1);
		}
		return ans;
	}

	for (int i = 1; i < n; i++) {
		if (protocol[i] == 0) col[i] = col[host[i]];
		else col[i] = !col[host[i]];
	}
	for (int i = 0; i < n; i++) if (!done[i]) {
		v[0] = v[1] = 0;
		dfs3(i);
		ans += max(v[0], v[1]);
	}
	return ans;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 284 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 472 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 1 ms 468 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Runtime error 26 ms 3144 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -