Submission #1074237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074237		pravcoder	Friend (IOI14_friend)	C++17	46 / 100	50 ms	65536 KiB

friend

#include "friend.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;
typedef vector<vb> v2b;

#define pb push_back
#define mp make_pair
#define rept(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)

vpi connections;
v2b adj;
v2i adj2;
vi bestincl;
vi bestexcl;
vi conf;

void connect(int a, int b) {
	//cout << "Connected " << a << " and " << b << "\n";
	if (a > b) swap(a, b);
	connections.pb({ a, b });
	adj[a][b] = true;
	adj[b][a] = true;
	adj2[a].pb(b);
	adj2[b].pb(a);
}

int findbestexcl(int u, int p);

int findbestincl(int u, int p=-2) {
	if (bestincl[u] != -1) return bestincl[u];
	else {
		int res = conf[u];
		for (auto v : adj2[u]) {
			if (v != p) {
				res += findbestexcl(v, u);
			}
		}
		bestincl[u] = res;
		return res;
	}
}

int findbestexcl(int u, int p = -2) {
	if (bestexcl[u] != -1) return bestexcl[u];
	else {
		int res = 0;
		for (auto v : adj2[u]) {
			if (v != p) {
				res += max(findbestincl(v, u), findbestexcl(v, u));
			}
		}
		bestexcl[u] = res;
		return res;
	}
}

// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
	bool sub1 = false;
	bool sub2 = true;
	bool sub3 = true;
	bool sub4 = true;
	adj.resize(n, vb(n));
	adj2.resize(n);

	if (n <= 10) {
		sub1 = true;
	}

	conf.pb(confidence[0]);

	rept(i, 1, n) {
		conf.pb(confidence[i]);
		int h = host[i];
		int prot = protocol[i];
		if (prot == 0) {
			sub3 = false;
			sub2 = false;
			connect(h, i);
		}
		else if (prot == 1) {
			sub3 = false;
			sub4 = false;
			rep(j, i) {
				if (j != h && adj[j][h]) {
					connect(j, i);
				}
			}
		}
		else {
			sub4 = false;
			sub2 = false;
			rep(j, i) {
				if (adj[j][h] || j == h) {
					connect(j, i);
				}
				else {
					//cout << "Didn't connect " << j << " and " << i << "\n";
				}
			}
		}
	}

	//------------debug------------
	//sub1 = false, sub2 = false, sub3 = false;
	//-----------------------------


	if (sub1) {
		vi sub(n);
		int maxc = 0;
		int totc = 0;
		rep(i, (1 << n) - 1) {
			//generate next subset
			int j = n-1;
			totc += confidence[j];
			while (++sub[j] > 1) {
				sub[j--] = 0;
				totc += confidence[j] - 2 * confidence[j+1];
			}
			// check if the subset is valid
			if (totc > maxc) {
				bool valid = true;
				for (int j = 0; j < connections.size() && valid; j++)
				{
					valid = !(sub[connections[j].first] && sub[connections[j].second]);
				}
				if (valid) {
					maxc = totc;
				}
			}
		}
		return maxc;
	}
	if (sub2) {
		int totc = 0;
		rep(i, n) {
			totc += confidence[i];
		}
		return totc;
	}
	if (sub3) {
		int maxc = 0;
		rep(i, n) {
			maxc = max(maxc, confidence[i]);
		}
		return maxc;
	}
	if (sub4) {
		bestincl.resize(n, -1);
		bestexcl.resize(n, -1);
		return max(findbestincl(0), findbestexcl(0));
	}
}

Compilation message (stderr)

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:137:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for (int j = 0; j < connections.size() && valid; j++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
friend.cpp:167:1: warning: control reaches end of non-void function [-Wreturn-type]
  167 | }
      | ^

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