Submission #582412

#	Time	Username	Problem	Language	Result	Execution time	Memory
582412		Josia	친구 (IOI14_friend)	C++14	35 / 100	190 ms	65536 KiB

friend

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

using namespace std;

vector<pair<int, int>> chef;
vector<set<int>> graph;




void init(int n, int values[]) {
	chef.clear();
	chef.resize(n);
	for (int i = 0; i<n; i++) {
		chef[i].first = i;
		chef[i].second = values[i];
	}

	graph.clear();
	graph.resize(n);
}




int find(int x) {
	if (chef[x].first == x) return x;
	return chef[x].first = find(chef[x].first);
}

void unite(int a, int b, bool addup) {
	if (find(a) == find(b)) return;


	if (graph[a].size() > graph[b].size()) swap(graph[a], graph[b]);
	for (int i: graph[find(a)]) {
		graph[find(b)].insert(i);
	}

	if (addup) chef[find(b)].second += chef[find(a)].second;
	else chef[find(b)].second = max(chef[find(b)].second, chef[find(a)].second);
	chef[find(a)].first = find(b);
}



pair<int, int> dfs(int v, vector<bool> &visited, vector<int> &val) {
	v = find(v);
	if (visited[v]) return {0, 0};
	visited[v] = 1;

	pair<int, int> res = {chef[find(v)].second, 0};

	for (int i: graph[v]) {
		pair<int, int> tmp = dfs(i, visited, val);
		res.first += tmp.second;
		res.second += tmp.first;
	}

	res.first = max(res.first, res.second);
	return res;
}




// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
	init(n, confidence);

	for (int i = 1; i<n; i++) {
		if (protocol[i] == 0) {
			graph[find(host[i])].insert(find(i));
			graph[find(i)].insert(find(host[i]));
		}
		if (protocol[i] == 1) {
			for (int j: graph[find(host[i])]) {
				unite(*graph[find(host[i])].begin(), j, 1);
			}
			if (graph[find(host[i])].empty()) continue;
			graph[find(*graph[find(host[i])].begin())].insert(find(i));
			graph[find(i)].insert(find(*graph[find(host[i])].begin()));
		}
		if (protocol[i] == 2) {
			for (int j: graph[find(host[i])]) {
				unite(*graph[find(host[i])].begin(), j, 1);
			}
			unite(i, host[i], 0);

			if (graph[find(host[i])].empty()) continue;
			graph[find(*graph[find(host[i])].begin())].insert(find(i));
			graph[find(i)].insert(find(*graph[find(host[i])].begin()));
		}
	}


	vector<bool> visited(n, 0);
	vector<int> values;

	for (int i = 0; i<n; i++) values.push_back(confidence[i]);

	int res = 0;
	
	for (int i = 0; i<n; i++) res += dfs(i, visited, values).first;

	return res;
}

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