Submission #385924

#	Time	Username	Problem	Language	Result	Execution time	Memory
385924		alireza_kaviani	Friend (IOI14_friend)	C++11	35 / 100	3 ms	2796 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"
using namespace std;

typedef pair<int, int> pii;

#define X			first
#define Y			second
#define all(x)		(x).begin() , (x).end()
#define SZ(x)		int(x.size())

const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;

int par[MAXN] , sz[MAXN] , val[MAXN] , dp[2][MAXN] , mark[MAXN];
vector<int> adj[MAXN];
vector<pii> E;

int Find(int v){
	return (par[v] == -1 ? v : par[v] = Find(par[v]));
}

void Union(int v , int u , int flag){
	v = Find(v); u = Find(u);
	if(v == u)	return;
	if(sz[v] < sz[u])	swap(v , u);
	par[u] = v; sz[v] += sz[u];
	if(flag == 0)	val[v] += val[u];
	if(flag == 1)	val[v] = max(val[v] , val[u]);
}

void DFS(int v , int p = -1){
	mark[v] = 1;
	dp[1][v] = val[v];
	for(int u : adj[v]){
		if(u == p)	continue;
		DFS(u , v);
		dp[0][v] += max(dp[0][u] , dp[1][u]);
		dp[1][v] += dp[0][u];
	}
}

int findSample(int n,int confidence[],int host[],int protocol[]){
	for(int i = 0 ; i < n ; i++){
		val[i] = confidence[i];
		par[i] = -1; sz[i] = 1;
	}
	for(int i = 1 ; i < n ; i++){
		if(protocol[i] == 0){
			E.push_back({i , host[i]});
		}
		else{
			Union(i , host[i] , (protocol[i] == 2));
		}
	}
	for(pii i : E){
		adj[Find(i.X)].push_back(Find(i.Y));
		adj[Find(i.Y)].push_back(Find(i.X));
	}
	int ans = 0;
	for(int i = 0 ; i < n ; i++){
		if(i == Find(i) && !mark[i]){
			DFS(i);
			ans += max(dp[0][i] , dp[1][i]);
		}
	}
	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