oj.uz

Submission #114429

# Submission time Handle Problem Language Result Execution time Memory
114429 2019-06-01T09:56:13 Z E869120 Friend (IOI14_friend) C++14
35 / 100
 7 ms 5200 KB 
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;

// --------------------------------- FLOW LIBRARY -----------------------

struct edge { int to, cap, rev; };

vector<edge> H[100009]; bool used[100009];

void add_edge(int u, int v, int w) {
	H[u].push_back(edge{v, w, (int)H[v].size()});
	H[v].push_back(edge{u, 0, (int)H[u].size() - 1});
}

int dfs1(int pos, int t, int f) {
	if (pos == t) return f;
	
	used[pos] = true;
	for (int i = 0; i < H[pos].size(); i++) {
		if (used[H[pos][i].to] == true || H[pos][i].cap == 0) continue;
		
		int F = dfs1(H[pos][i].to, t, min(f, H[pos][i].cap));
		H[pos][i].cap -= F;
		H[H[pos][i].to][H[pos][i].rev].cap += F;
		return F;
	}
	return 0;
}

int max_flow(int u, int v) {
	int ans = 0;
	while (true) {
		for (int i = 0; i < 1009; i++) used[i] = false;
		int FF = dfs1(u, v, 1000000007);
		if (FF == 0) return ans;
		ans += FF;
	}
}

// --------------------------------- FLOW LIBRARY -----------------------

vector<int> G[100009];
int dp[100009][2], A[100009], col[100009];

void dfs(int pos) {
	int m1 = 0, m2 = 0;
	for (int i = 0; i < G[pos].size(); i++) {
		dfs(G[pos][i]);
		m1 += max(dp[G[pos][i]][0], dp[G[pos][i]][1]);
		m2 += dp[G[pos][i]][1];
	}
	m2 += A[pos];
	dp[pos][0] = m2; dp[pos][1] = m1;
}

void dfs2(int pos, int dep) {
	if (col[pos] >= 0) return;
	col[pos] = dep;
	for (int i = 0; i < G[pos].size(); i++) dfs2(G[pos][i], dep ^ 1);
}

// Find out best sample
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) {
		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);
				}
			}
		}
		
		for (int i = 0; i < n; i++) col[i] = -1;
		for (int i = 0; i < n; i++) {
			if (col[i] >= 0) continue;
			dfs2(i, 0);
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < G[i].size(); j++) {
				if (col[i] == 0 && col[G[i][j]] == 1) add_edge(i, G[i][j], 1);
			}
			if (col[i] == 0) add_edge(n, i, 1);
			if (col[i] == 1) add_edge(i, n + 1, 1);
		}
		int R = max_flow(n, n + 1);
		return n - R;
	}
	if (bit == 1) {
		// Subtask 4.
		for (int i = 0; i < n; i++) A[i] = confidence[i];
		for (int i = 1; i <= n - 1; i++) G[host[i]].push_back(i);
		dfs(0);
		return max(dp[0][0], dp[0][1]);
	}
	if (bit == 2) {
		// Subtask 2.
		int sum = 0; for (int i = 0; i < n; i++) sum += confidence[i];
		return sum;
	}
	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.
		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 'int dfs1(int, int, int)':
friend.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < H[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
friend.cpp: In function 'void dfs(int)':
friend.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
friend.cpp: In function 'void dfs2(int, int)':
friend.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[pos].size(); i++) dfs2(G[pos][i], dep ^ 1);
                  ~~^~~~~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:89:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < G[i].size(); j++) {
                    ~~^~~~~~~~~~~~~
friend.cpp:135: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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 5 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 5 ms 4992 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 5 ms 4992 KB Output is correct
8 Incorrect 6 ms 4992 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 6 ms 5200 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 4992 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 6 ms 4992 KB Output is correct
11 Correct 6 ms 4992 KB Output is correct
12 Correct 6 ms 5120 KB Output is correct
13 Correct 6 ms 5120 KB Output is correct
14 Correct 6 ms 4992 KB Output is correct
15 Correct 7 ms 5120 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 5 ms 4992 KB Output is correct
3 Correct 5 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Incorrect 6 ms 4992 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5092 KB Output is correct
2 Correct 5 ms 4992 KB Output is correct
3 Incorrect 6 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -