Submission #564766

#	Time	Username	Problem	Language	Result	Execution time	Memory
564766		hoanghq2004	Friend (IOI14_friend)	C++14	100 / 100	28 ms	3000 KiB

friend

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "friend.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e5 + 10;

int findSample(int n, int f[], int p[], int type[]) {
    int g[n];
    memset(g, 0, sizeof(g));
    for (int v = n - 1; v > 0; --v) {
        int u = p[v];
        if (type[v] == 0) {
            f[u] += g[v];
            g[u] += max(f[v], g[v]);
        } else if (type[v] == 2) {
            int nf = max(f[u] + g[v], g[u] + f[v]);
            int ng = g[u] + g[v];
            f[u] = nf;
            g[u] = ng;
        } else {
            int nf = max({f[u] + f[v], f[u] + g[v], f[v] + g[u]});
            int ng = g[u] + g[v];
            f[u] = nf;
            g[u] = ng;
        }
    }
    return max(f[0], g[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