| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1050884 | AnhPham | Friend (IOI14_friend) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#ifdef OP_DEBUG
#include <algo/debug.h>
#else
#define debug(...) 26
#endif
using namespace std;
template <class Fun> class y_combinator_result {
Fun fun_;
public:
template <class T> explicit y_combinator_result(T &&fun): fun_(std::forward <T> (fun)) {}
template <class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward <Args> (args)...); }
};
template <class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result <std::decay_t <Fun>> (std::forward <Fun> (fun)); }
#define int long long
#define eb emplace_back
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define TcT template <class T
const int MOD = (int)1e9 + 7, INF = (int)4e18 + 18;
TcT> bool minimize(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }
TcT> bool maximize(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }
void solve();
int32_t main() {
cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(false);
int testcases = 1;
#define multitest 0
if (multitest) { cin >> testcases; } for (; testcases--;) { solve(); }
}
/* [Pham Hung Anh - 12I - Tran Hung Dao High School for Gifted Student] */
const int mxN = 1e5 + 5;
int N;
int C[mxN];
int host[mxN], protocol[mxN];
int is_friend[1001][1001]; // just use for sub12345
namespace sub1 {
void solve() {
int ans = 0;
for (int mask = 0; mask < (1 << N); ++mask) {
int cur_ans = 0, invalid = 0;
for (int i = 0; i < N; ++i) {
if ((mask >> i & 1) == 0)
continue;
for (int j = 0; j < N; ++j) {
if (is_friend[i][j] == 0 || i == j)
continue;
if (mask >> j & 1) {
invalid = 1;
break;
}
}
if (invalid)
break;
cur_ans += C[i];
}
if (invalid == 0)
maximize(ans, cur_ans);
}
cout << ans << '\n';
}
}
namespace sub2 {
bool check() {
for (int i = 1; i < N; ++i) if (protocol[i] != 1)
return 0;
return 1;
}
void solve() { // your friends not my friends
int ans = 0;
for (int i = 0; i < N; ++i)
ans += C[i];
cout << ans << '\n';
}
}
namespace sub3 {
bool check() {
for (int i = 1; i < N; ++i) if (protocol[i] != 2)
return 0;
return 1;
}
void solve() { // we are friends
int ans = 0;
for (int i = 1; i < N; ++i)
maximize(ans, C[i]);
cout << ans << '\n';
}
}
namespace sub4 {
bool check() {
for (int i = 1; i < N; ++i) if (protocol[i] != 0)
return 0;
return 1;
}
int dp[1001][2];
int vst[1001];
void solve() {
memset(dp, -1, sizeof (dp));
auto dfs = y_combinator([&](auto self, int u, int p) -> void {
vst[u] = 1;
for (int v = 0; v < N; ++v) {
if (is_friend[u][v] == 0)
continue;
if (v == p || v == u)
continue;
self(v, u);
}
});
auto calc = y_combinator([&](auto self, int u, int p, bool can_take) -> int {
if (dp[u][can_take] != -1)
return dp[u][can_take];
int res = 0;
if (can_take == 0) {
int cur_res = 0;
for (int v = 0; v < N; ++v) {
if (is_friend[u][v] == 0)
continue;
cur_res += self(v, u, 1);
}
maximize(res, cur_res);
} else {
int cur_res = C[u];
for (int v = 0; v < N; ++v) {
if (is_friend[u][v] == 0)
continue;
cur_res += self(v, u, 0);
}
maximize(res, cur_res);
}
return dp[u][can_take] = res;
});
int ans = 0;
for (int u = 0; u < N; ++u)
if (vst[u] == 0) {
dfs(u, -1);
ans += calc(u, -1, 1);
}
cout << ans << '\n';
}
}
namespace sub5 {
bool check() {
for (int i = 1; i < N; ++i) if (protocol[i] == 2)
return 0;
return 1;
}
void solve() {
}
}
void solve() {
cin >> N;
for (int i = 0; i < N; ++i)
cin >> C[i];
for (int i = 1; i < N; ++i)
cin >> host[i] >> protocol[i];
if (N <= 1000) {
for (int i = 1; i < N; ++i) {
int h = host[i], p = protocol[i];
if (p == 0) // i'am your friend, not your friends
is_friend[i][h] = is_friend[h][i] = 1;
else if (p == 1) { // your friend are my friend, not you
for (int j = 0; j < N; ++j) {
if (is_friend[h][j] == 0)
continue;
is_friend[i][j] = is_friend[j][i] = 1;
}
} else { // we are friend
is_friend[i][h] = is_friend[h][i] = 1;
for (int j = 0; j < N; ++j) {
if (is_friend[h][j] == 0)
continue;
is_friend[i][j] = is_friend[j][i] = 1;
}
}
}
if (N <= 10)
sub1 :: solve();
else if (sub2 :: check())
sub2 :: solve();
else if (sub3 :: check())
sub3 :: solve();
else if (sub4 :: check())
sub4 :: solve();
else if (sub5 :: check())
sub5 :: solve();
}
}