oj.uz

Submission #780241

# Submission time Handle Problem Language Result Execution time Memory
780241 2023-07-12T07:37:26 Z Sohsoh84 Friend (IOI14_friend) C++17
0 / 100
 40 ms 58300 KB 
#include "friend.h"
#include <bits/stdc++.h>

using namespace std;

#define debug(x)		cerr << #x << ": " << x << endl;

const int MAXN = 1e6 + 10;

int dp[MAXN];
vector<int> adj[MAXN];

inline void add(int u, int v) {
	adj[u].push_back(v);
	adj[v].push_back(u);
}

int findSample(int n, int C[], int host[], int protocol[]){
	for (int i = 1; i < n; i++) {
		if (protocol[i] % 2 == 0) add(host[i], i);
		if (protocol[i] > 0) {
			for (int u : adj[host[i]])
				add(i, u);
		}
	}

	for (int mask = 1; mask < (1 << n); mask++) {
		int v = __builtin_ctz(mask);
		dp[mask] = dp[mask ^ (1 << v)];

		int tmask = (1 << v);
		for (int u : adj[v])
			tmask |= (1 << u);

		dp[mask] = max(dp[mask], dp[(mask | tmask) ^ tmask] + C[v]);
	}

	return dp[(1 << n) - 1];
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 23764 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 40 ms 58300 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 47968 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 23808 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 23680 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 23772 KB Memory limit exceeded
2 Halted 0 ms 0 KB -