Submission #1042161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042161		pawned	Friend (IOI14_friend)	C++17	35 / 100	15 ms	4316 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 cr(MAX);	// c, taken maximum over equiv

vi hs(MAX);

vi type(MAX);

vi base(MAX);	// top vertex mapped to

vi adj[MAX];

vector<bool> vis(MAX, false);
vector<ll> s1(MAX, 0);	// max sum if use vertex
vector<ll> s2(MAX, 0);	// max sum if not use vertex

void dfs(int n) {
	vis[n] = true;
	s1[n] = cr[n];
	for (int x : adj[n]) {
		if (!vis[x] && cr[x] != 0) {
			dfs(x);
			s2[n] += max(s1[x], s2[x]);
			s1[n] += s2[x];
		}
	}

}

void reset() {
	for (int i = 0; i < N; i++) {
		c[i] = 0;
		cr[i] = 0;
		hs[i] = 0;
		type[i] = 0;
		base[i] = 0;
		adj[i].clear();
		vis[i] = false;
		s1[i] = 0;
		s2[i] = 0;
	}
}

int findSample(int n, int confidence[], int hst[], int protocol[]) {
	N = n;
	reset();
	for (int i = 0; i < N; i++) {
		c[i] = confidence[i];
		cr[i] = confidence[i];
		hs[i] = hst[i];
		type[i] = protocol[i];
		base[i] = 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 {
			base[i] = base[hs[i]];
			cr[base[i]] = max(cr[base[i]], c[i]);
			cr[i] = 0;
		}
	}
/*	cout<<"adj: "<<endl;
	for (int i = 0; i < N; i++) {
		cout<<i<<": ";
		for (int x : adj[i])
			cout<<x<<" ";
		cout<<endl;
	}
	cout<<"cr: ";
	for (int i = 0; i < N; i++) {
		cout<<cr[i]<<" ";
	}
	cout<<endl;*/
	// have bipartite graph w/o cycles, do bfs
	vi heads;
	for (int i = 0; i < N; i++) {
		if (!vis[i] && (cr[i] != 0)) {
			heads.pb(i);
			dfs(i);
		}
	}
/*	cout<<"s1: ";
	for (int i = 0; i < N; i++) {
		cout<<s1[i]<<" ";
	}
	cout<<endl;
	cout<<"s2: ";
	for (int i = 0; i < N; i++) {
		cout<<s2[i]<<" ";
	}
	cout<<endl;
	cout<<"heads: ";
	for (int x : heads)
		cout<<x<<" ";
	cout<<endl;*/
	ll total = 0;
	for (int x : heads) {
		total += max(s1[x], s2[x]);
	}
	return (int)(total);
}

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