Submission #1276162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276162		KindaGoodGames	Friend (IOI14_friend)	C++17	19 / 100	2 ms	588 KiB

friend

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

using namespace std;

struct UnionFind{
	vector<int> par;

	UnionFind(int n){
		par.resize(n);
		iota(par.begin(),par.end(),0);
	}

	int find(int i){
		if(par[i] == i) return i;
		return par[i] = find(par[i]);
	}

	void unite(int i, int j){
		i = find(i);
		j = find(j);
		par[i] = j;
	}
};

vector<int> arr,dpT, dpN;
	vector<vector<int>> adj;

void DFS(int v){
	dpT[v] = arr[v];
	int oth1 = 0;

	for(auto u : adj[v]){
		DFS(u);
		dpT[v] += dpN[u];
		dpN[v] += max(dpT[u],dpN[u]);
	}
}

// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
	int ans=0;
	adj.resize(n);
	for(int i = 1; i < n; i++){
		adj[host[i]].push_back(i);
	}
	arr.resize(n);
	dpT.resize(n);
	dpN.resize(n);
	for(int i = 0; i < n; i++){
		arr[i] = confidence[i];
	}

	DFS(0);
	for(int i = 0; i < n; i++){
		ans = max({ans, dpT[i], dpN[i]});
	}
	return ans;
}

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