Submission #62890

#	Time	Username	Problem	Language	Result	Execution time	Memory
62890		zadrga	Friend (IOI14_friend)	C++14	35 / 100	8 ms	3716 KiB

friend

// 19.07

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

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF ((int) 1e9)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 100111

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

int val[maxn], root[maxn], dp[maxn][2];

vector<pii> edge;
vector<int> adj[maxn];
bool used[maxn];

int rooting(int x){
	if(root[x] == x)
		return x;

	return root[x] = rooting(root[x]);
}

void DFS(int x, int p){
	dp[x][0] = 0;
	dp[x][1] = val[x];
	used[x] = 1;

	for(int v : adj[x]){
		if(v == p)
			continue;
		DFS(v, x);
	}

	for(int v : adj[x]){
		if(v == p)
			continue;

		dp[x][0] += max(dp[v][1], dp[v][0]);
		dp[x][1] += dp[v][0];
	}
}

int findSample(int n, int confidence[], int host[], int protocol[]){
	for(int i = 0; i < n; i++){
		val[i] = confidence[i];
		root[i] = i;
	}

	for(int i = n - 1; i > 0; i--){
		int a = host[i];
		int b = i;

		if(protocol[i] == 0)
			edge.pb(mp(a, b));

		if(protocol[i] != 0){
			int ra = rooting(a);
			int rb = rooting(b);
			root[rb] = ra;
			if(protocol[i] == 1)
				val[ra] += val[rb];

			if(protocol[i] == 2)
				val[ra] = max(val[ra], val[rb]);

			val[rb] = 0;
		}
	}

	for(pii e : edge){
		int a = rooting(e.fi);
		int b = rooting(e.se);
		adj[a].pb(b);
		adj[b].pb(a);
	}

	int ans = 0;
	for(int i = 0; i < n; i++){
		if(!used[i]){
			DFS(i, -1);
			ans += max(dp[i][0], dp[i][1]);
		}
	}

	return ans;
}

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