Submission #1268109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268109		herominhsteve	Friend (IOI14_friend)	C++20	100 / 100	17 ms	3516 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"
#define allof(x) x.begin(),x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

struct Query{
	int u,v,type;
	Query(): u(0),v(0),type(0) {}
	Query(int U,int V,int T): u(U), v(V), type(T) {}
};

int findSample(int n, int confidence[], int host[], int protocol[]){
	vector<Query> queries;
	for (int i=1;i<n;i++) queries.emplace_back(host[i],i,protocol[i]);
	reverse(allof(queries));
	int dp[n+1][2];
	mset(dp,0);
	for (int i=0;i<n;i++) dp[i][1] = confidence[i];
	for (Query qr : queries){
		int type = qr.type;
		int u = qr.u;
		int v = qr.v;
		if (!type){
			dp[u][1] += dp[v][0];
			dp[u][0] += max(dp[v][1],dp[v][0]);
		} else if (type==1){
			dp[u][1] = max({dp[u][1] + dp[v][0],dp[u][0] + dp[v][1],dp[u][1] + dp[v][1]});
			dp[u][0] += dp[v][0];
		} else{
			dp[u][1] = max(dp[u][1] + dp[v][0],dp[u][0] + dp[v][1]);
			dp[u][0] += dp[v][0]; 
		}
	}
	return max(dp[0][0],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