Submission #1042208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042208		pawned	Friend (IOI14_friend)	C++17	11 / 100	1078 ms	3824 KiB

friend

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "friend.h"

const int MAX = 1005;

int N;

vi c(MAX);

vi hs(MAX);

vi type(MAX);


vi adj[MAX];

void reset() {
	for (int i = 0; i < N; i++) {
		c[i] = 0;
		hs[i] = 0;
		type[i] = 0;
		adj[i].clear();
	}
}

int findSample(int n, int confidence[], int hst[], int protocol[]) {
	N = n;
	reset();
	for (int i = 0; i < N; i++) {
		c[i] = confidence[i];
		hs[i] = hst[i];
		type[i] = protocol[i];
	}
	for (int i = 1; i < N; i++) {
		if (type[i] == 0) {
			adj[i].pb(hs[i]);
			adj[hs[i]].pb(i);
		}
		else if (type[i] == 1) {
			for (int x : adj[hs[i]]) {
				adj[i].pb(x);
				adj[x].pb(i);
			}
		}
		else if (type[i] == 2) {
			for (int x : adj[hs[i]]) {
				adj[i].pb(x);
				adj[x].pb(i);
			}
			adj[i].pb(hs[i]);
			adj[hs[i]].pb(i);
		}
	}
/*	cout<<"adj: "<<endl;
	for (int i = 0; i < N; i++) {
		cout<<i<<": ";
		for (int x : adj[i])
			cout<<x<<" ";
		cout<<endl;
	}*/
	ll maximum = 0;
	for (int b = 0; b < (1 << N); b++) {
		bool works = true;
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (((b & (1 << i)) != 0) && ((b & (1 << j)) != 0)) {
					bool in = false;
					for (int k : adj[i])
						if (k == j)
							in = true;
					if (in)
						works = false;
				}
			}
		}
		if (!works)
			continue;
		ll sum = 0;
		for (int i = 0; i < N; i++) {
			if (b & (1 << i))
				sum += c[i];
		}
		maximum = max(maximum, sum);
	}
	return maximum;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31