Submission #385987

#	Time	Username	Problem	Language	Result	Execution time	Memory
385987		mehrdad_sohrabi	Friend (IOI14_friend)	C++14	100 / 100	48 ms	9452 KiB

friend

// Black lives matter
#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
typedef long long int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=1e5+10;
ll val[N];
ll s[N];
ll jam[N];
ll par[N];
vector <pii> g[N];
ll dp[N][2];
/// 0 varnadare 1 vardare

int32_t findSample(int32_t n,int32_t confidence[],int32_t host[],int32_t protocol[]){
	for (int i=0;i<n;i++) val[i]=confidence[i],par[i]=i,dp[i][1]=val[i];
	for (int i=1;i<n;i++){
            /// 0 yal adi
            /// 1 yal tosi
            /// 2 yal ghermez
        if (protocol[i]==0){
            g[par[host[i]]].pb({i,protocol[i]});
        }
        if (protocol[i]){
            par[i]=par[host[i]];
            g[host[i]].pb({i,protocol[i]});
        }
	}
//	for (int i=1;i<n;i++) cout << protocol[i] << " ";
	//cout << endl;
	for (int i=n-1;i>0;i--){
        if (protocol[i]==0){
            dp[host[i]][0]+=max(dp[i][1],dp[i][0]);
            dp[host[i]][1]+=dp[i][0];
            continue;
        }
        if (protocol[i]==1){
        //if (host[i]==1) cout << i << " " << dp[1][1] << " " << dp[1][0] << " " << dp[i][1] << " " << dp[i][0] << endl;
            dp[host[i]][1]=max(dp[host[i]][0]+dp[i][1],max(dp[host[i]][1]+dp[i][1],dp[host[i]][1]+dp[i][0]));
            dp[host[i]][0]+=dp[i][0];
         //   dp[host[i]][1]=max(dp[host[i]][1],dp[host[i]][0]+dp[i][0]);
            continue;
        }
        dp[host[i]][1]=max(dp[host[i]][1]+dp[i][0],dp[host[i]][0]+dp[i][1]);
        dp[host[i]][0]+=dp[i][0];
        
	}
	//cout << dp[1][1] << endl;
	return max(dp[0][0],dp[0][1]);
}
/*
// Confidence
int32_t confidence[N];

// Host
int32_t host[N];


int32_t protocol[N];

// Main
int32_t main(void)
{
	int n,i;

	// Number of people
	assert(scanf("%d",&n)==1);

	// Confidence
	for(i=0;i<n;i++)
		assert(scanf("%d",&confidence[i])==1);

	// Host and Protocol
	for(i=1;i<n;i++){
		scanf("%d %d",&host[i],&protocol[i]);
		//cout << protocol[i] << endl;
	}
	// Answer
	printf("%d\n",findSample(n,confidence,host,protocol));
	return 0;
}
*/

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