Submission #289651

#	Time	Username	Problem	Language	Result	Execution time	Memory
289651		shayan_p	Friend (IOI14_friend)	C++17	100 / 100	61 ms	8568 KiB

friend

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

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k))&1)

using namespace std;

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

const int maxn = 1e5 + 10, mod = 1e9 + 7;

vector<int> v[maxn];
int dp[maxn][2], state[maxn], a[maxn], tmp[maxn];

void dfs(int u){
    reverse(v[u].begin(), v[u].end());

    dp[u][1] = a[u];
    for(int y : v[u]){
	dfs(y);
	tmp[y] = dp[u][0];
	if(state[y] != 0)
	    dp[u][0]+= dp[y][0];
	else
	    dp[u][0]+= dp[y][1];
	if(state[y] == 1)
	    dp[u][1]+= dp[y][1];
	else
	    dp[u][1]+= dp[y][0];
    }

    reverse(v[u].begin(), v[u].end());

    int num = 0;
    for(int y : v[u]){
	if(state[y] == 0)
	    dp[u][1] = max(dp[u][1], tmp[y] + dp[y][1] + num);
	if(state[y] == 2)
	    dp[u][1] = max(dp[u][1], tmp[y] + dp[y][1] + num);
	if(state[y] == 1)
	    num+= dp[y][1];
	else
	    num+= dp[y][0];
    }
}

int findSample(int n,int confidence[],int host[],int protocol[]){
    for(int i = 1; i < n; i++){
	v[host[i]].PB(i);
	state[i] = protocol[i];
    }
    for(int i = 0; i < n; i++){
	a[i] = confidence[i];
    }
    dfs(0);
    return dp[0][1];
}

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