Submission #644580

#	Time	Username	Problem	Language	Result	Execution time	Memory
644580		ymm	Friend (IOI14_friend)	C++17	100 / 100	39 ms	7252 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

enum {
	FWP = 1,
	FWFP = 2,
};

const int N = 100010;
vector<pii> A[N];
int val[N];
int n;

pii dfs(int v)
{
	int ans0 = 0, ans10 = 0, ans11 = val[v], sum10 = 0;
	vector<pii> vec;
	for (auto [u, proto] : A[v]) {
		auto [x, y] = dfs(u); // x <= y
		ans0 += proto & FWFP? x: y;
		sum10 += proto & FWFP? x: y;
		ans11 += proto & FWP? x: y;
		vec.push_back({x, y});
	}
	Loop (i,0,A[v].size()) {
		auto [u, proto] = A[v][i];
		auto [x, y] = vec[i];
		sum10 -= proto & FWFP? x: y;
		sum10 += y;
		ans10 = max(ans10, sum10);
		sum10 -= y;
		sum10 += proto & FWP? x: y;
	}
	return {ans0, max(ans10, ans11)};
}

// Find out best sample
int findSample(int n, int confidence[], int host[], int protocol[])
{
	::n = n;
	Loop (i,1,n)
		A[host[i]].push_back({i, protocol[i]+1});
	Loop (i,0,n)
		val[i] = confidence[i];
	return dfs(0).second;
}

Compilation message (stderr)

friend.cpp: In function 'pii dfs(int)':
friend.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
friend.cpp:31:2: note: in expansion of macro 'Loop'
   31 |  Loop (i,0,A[v].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