Submission #1276166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276166		KindaGoodGames	Friend (IOI14_friend)	C++17	27 / 100	2 ms	584 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[j] = i;
	}
};

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);
	arr.resize(n);
	arr[0] = confidence[0];
	UnionFind uf(n);
	for(int i = 1; i < n; i++){
		if(protocol[i] == 0){ 
			adj[host[i]].push_back(i);  
			arr[i] = confidence[i];
		}else{
			uf.unite(host[i],i);
			int real =uf.find(i); 
			arr[real] += confidence[i];
		}
	}  

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

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