oj.uz

Submission #355518

# Submission time Handle Problem Language Result Execution time Memory
355518 2021-01-22T15:54:55 Z Mefarnis Friend (IOI14_friend) C++14
46 / 100
 40 ms 6380 KB 
#include <bits/stdc++.h>
#include "friend.h"
#define maxn 1000
#define pb push_back
using namespace std;

int n;
int dp[maxn][2];
bool mat[maxn][maxn];
vector<int> scores;
vector<int> adj[maxn];

int solve1() {
	int res = 0;
	int N = (1<<n);
	for( int bmask = 1 ; bmask < N ; bmask++ ) {
		int sum = 0;
		vector<int> vec;
		for( int i = 0 ; i < n ; i++ )
			if(bmask&(1<<i)) {
				vec.pb(i);
				sum += scores[i];
			}
		int sz = vec.size();
		bool ok = true;
		for( int i = 0 ; i < sz ; i++ )
			for( int j = 0 ; j < sz ; j++ ) {
				int u = vec[i];
				int v = vec[j];
				if(mat[u][v])
					ok = false;
			}
		if(ok)
			res = max(res,sum);
	}
	return res;
}

int solve2() {
	int sum = 0;
	for( int i = 0 ; i < n ; i++ )
		sum += scores[i];
	return sum;
}

int solve3() {
	int mx = 0;
	for( int i = 0 ; i < n ; i++ )
		mx = max(mx,scores[i]);
	return mx;
}

int f(int u , int st , int dad) {
	if(dp[u][st] != -1)
		return dp[u][st];
	dp[u][st] = 0;
	int deg = adj[u].size();
	for( int i = 0 ; i < deg ; i++ ) {
		int v = adj[u][i];
		if(v != dad)
			dp[u][st] += f(v,1,u);
	}
	if(st) {
		int sum = scores[u];
		for( int i = 0 ; i < deg ; i++ ) {
			int v = adj[u][i];
			if(v != dad)
				sum += f(v,0,u);
		}
		dp[u][st] = max(dp[u][st],sum);
	}
	return dp[u][st];
}

int solve4() {
	memset(dp,-1,sizeof(dp));
	return f(0,1,-1);
}

int findSample(int N, int score[], int host[], int type[]) {
	n = N;
	int ans = 0;
	scores.pb(score[0]);
	for( int i = 1 ; i < N ; i++ ) {
		scores.pb(score[i]);
		int u = host[i];
		if(type[i] == 0) {
			adj[i].pb(u);
			adj[u].pb(i);
			mat[u][i] = mat[i][u] = true;
		}
		else if(type[i] == 1) {
			int deg = adj[u].size();
			for( int j = 0 ; j < deg ; j++ ) {
				int to = adj[u][j];
				adj[i].pb(to);
				adj[to].pb(i);
				mat[to][i] = mat[i][to] = true;
			}
		}
		else {
			int deg = adj[u].size();
			for( int j = 0 ; j < deg ; j++ ) {
				int to = adj[u][j];
				adj[i].pb(to);
				adj[to].pb(i);
				mat[to][i] = mat[i][to] = true;
			}
			adj[i].pb(u);
			adj[u].pb(i);
			mat[u][i] = mat[i][u] = true;
		}
	}
	if(n <= 10)
		ans = solve1();
	else if(type[1] == 1)
		ans = solve2();
	else if(type[1] == 2)
		ans = solve3();
	else if(type[1] == 0)
		ans = solve4();
	return ans;
}

/*
int main() {
	
	return 0;
}
*/

Subtask #1
11.0 / 11.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1644 KB Output is correct
2 Correct 13 ms 5100 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 8 ms 3820 KB Output is correct
5 Correct 13 ms 5100 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 1260 KB Output is correct
8 Correct 3 ms 1516 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 15 ms 5484 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
6 Correct 1 ms 1388 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 1388 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 876 KB Output is correct
12 Correct 1 ms 1388 KB Output is correct
13 Correct 1 ms 1260 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 1260 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 1516 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Incorrect 1 ms 876 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 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Runtime error 40 ms 6380 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -