Submission #582746

#	Time	Username	Problem	Language	Result	Execution time	Memory
582746		Josia	Friend (IOI14_friend)	C++14	27 / 100	9 ms	396 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"

using namespace std;


vector<vector<pair<int, int>>> graph;
vector<int> value;


vector<bool> visited;
pair<int, int> dfs(int v) {
	if (visited[v]) return {0, 0};
	visited[v] = 1;
	cerr << v << "\n";

	pair<int, int> res = {value[v], 0};

	for (auto i: graph[v]) {
		pair<int, int> tmp = dfs(i.first);
		if (i.second == 0) {
			res.first += tmp.second;
			res.second += tmp.first;
		}
		if (i.second == 1) {
			res.first += tmp.first;
			res.second += tmp.second;
		}
		if (i.second == 2) {
			res.first += tmp.second;
			res.second = max(res.second, tmp.first);
		}
	}
	res.first = max(res.first, res.second);
	cerr << res.first << " " << res.second << "\n";
	return res;
}



// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
	value.clear();
	graph.clear();
	graph.resize(n);
	value.resize(n);
	for (int i = 0; i<n; i++) value[i] = confidence[i];

	for (int i=1; i<n; i++) {
		graph[i].push_back({host[i], protocol[i]});
		graph[host[i]].push_back({i, protocol[i]});
	}

	visited.assign(n, 0);

	return dfs(0).first;
}

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