Submission #517022

#	Time	Username	Problem	Language	Result	Execution time	Memory
517022		AdamGS	Friend (IOI14_friend)	C++17	100 / 100	43 ms	8004 KiB

friend

#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
vector<pair<int,int>>V[LIM];
int T[LIM], dp[LIM][2];
void DFS(int x) {
	dp[x][1]=T[x];
	for(auto i : V[x]) {
		DFS(i.st);
		if(i.nd==0) dp[x][0]+=max(dp[i.st][0], dp[i.st][1]);
		else dp[x][0]+=dp[i.st][0];
		if(i.nd==1) dp[x][1]+=max(dp[i.st][0], dp[i.st][1]);
		else dp[x][1]+=dp[i.st][0];
	}
	int suf[V[x].size()+1];
	suf[V[x].size()]=0;
	for(int i=V[x].size()-1; i>=0; --i) {
		suf[i]=suf[i+1];
		if(V[x][i].nd==0) suf[i]+=max(dp[V[x][i].st][0], dp[V[x][i].st][1]);
		else suf[i]+=dp[V[x][i].st][0];
	}
	int akt=0;
	rep(i, V[x].size()) {
		if(V[x][i].nd==1) {
			akt+=max(dp[V[x][i].st][0], dp[V[x][i].st][1]);
		} else {
			dp[x][1]=max(dp[x][1], akt+max(dp[V[x][i].st][0], dp[V[x][i].st][1])+suf[i+1]);
			akt+=dp[V[x][i].st][0];
		}
	}
}
int findSample(int n, int confidence[], int host[], int protocol[]) {
	rep(i, n) T[i]=confidence[i];
	for(int i=1; i<n; ++i) V[host[i]].pb({i, protocol[i]});
	DFS(0);
	return max(dp[0][0], dp[0][1]);
}

Compilation message (stderr)

friend.cpp: In function 'void DFS(int)':
friend.cpp:6:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
friend.cpp:31:2: note: in expansion of macro 'rep'
   31 |  rep(i, V[x].size()) {
      |  ^~~

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