Submission #586375

#	Time	Username	Problem	Language	Result	Execution time	Memory
586375		SeDunion	Friend (IOI14_friend)	C++17	0 / 100	1 ms	688 KiB

friend

#include "friend.h"
#include<iostream>
#include<assert.h>
#include<vector>

using namespace std;

const int N = 1e4 + 123;

vector<int>g[N];
int c[N];

int used[N];

void dfs(int v, int &a, int &b) {
	a += c[v];
	used[v] = 1;
	for (int to : g[v]) if (!used[to]) {
		dfs(to, b, a);
	}
}

vector<int>vec;

int pr[N];

void go(int v) {
	used[v] = 1;
	for (int to : g[v]) if (to != pr[v]) {
		if (used[to]) {
			if (vec.size()) continue;
			int y = v;
			while (y != to) {
				vec.emplace_back(y);
				y = pr[y];
			}
			vec.emplace_back(to);
		} else {
			pr[to] = v;
			go(to);
		}
	}
}

int X[N], Y[N];

int dp[N][2];

int findSample(int n,int confidence[],int host[],int protocol[]){
	for (int i = 0 ; i < n ; ++ i) {
		c[i] = confidence[i];
	}
	for (int i = 1 ; i < n ; ++ i) {
		int j = host[i];
		g[j].emplace_back(i);
		g[i].emplace_back(j);
	}
	int ans = 0;
	for (int i = 0 ; i < n ; ++ i) {
		if (used[i]) continue;
		vec.clear();
		pr[i] = -1;
		go(i);
		for (int j = 0 ; j < n ; ++ j) used[j] = 0;
		if (!vec.size()) {
			int a = 0, b = 0;
			dfs(i, a, b);
			ans += max(a, b);
			continue;
		}
		for (int j : vec) used[j] = 1;
		int m = vec.size();
		for (int j = 0 ; j < m ; ++ j) {
			dfs(vec[j], X[j], Y[j]);
		}
		dp[0][0] = Y[0];
		dp[0][1] = 0;
		for (int j = 1 ; j < m ; ++ j) {
			dp[j][0] = max(dp[j - 1][0], dp[j - 1][1]) + Y[j];
			dp[j][1] = dp[j - 1][0] + X[j];
		}
		int cur = dp[m - 1][0];
		cur = max(cur, dp[m - 1][1]);
		dp[0][0] = 0;
		dp[0][1] = X[0];
		for (int j = 1 ; j < m ; ++ j) {
			dp[j][0] = max(dp[j - 1][0], dp[j - 1][1]) + Y[j];
			dp[j][1] = dp[j - 1][0] + X[j];
		}
		cur = max(cur, dp[m - 1][0]);
		ans += cur;
	}
	return ans;
}

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