Submission #1074128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074128		pravcoder	Friend (IOI14_friend)	C++17	27 / 100	45 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;

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);
}

// 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;
	}

	rept(i, 1, n) {
		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";
				}
			}
		}
	}
	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;
	}
}

Compilation message (stderr)

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:95: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]
   95 |     for (int j = 0; j < connections.size() && valid; j++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
friend.cpp:42:7: warning: variable 'sub4' set but not used [-Wunused-but-set-variable]
   42 |  bool sub4 = true;
      |       ^~~~
friend.cpp:120:1: warning: control reaches end of non-void function [-Wreturn-type]
  120 | }
      | ^

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