Submission #298604

#	Time	Username	Problem	Language	Result	Execution time	Memory
298604		emil_physmath	Friend (IOI14_friend)	C++17	100 / 100	38 ms	7416 KiB

friend

#include <algorithm>
#include <numeric>
#include <vector>
#include <set>
#include "friend.h"
using namespace std;
using llong = long long;
const int maxN = 100'005;
 
set<int> nei[maxN];
 
enum Protocol { ME = 0, MY = 1, WE = 2 };
pair<int, int> SolveTree(int v, int* a)
{
    pair<int, int> res(a[v], 0);
    for (int to: nei[v])
    {
        pair<int, int> cur = SolveTree(to, a);
        res.first += cur.second;
        res.second += max(cur.first, cur.second);
    }
    return res;
}
int findSample(int n, int a[], int host[], int prot[]) {
    if (count(prot + 1, prot + n, ME) == n - 1) {
        for (int i = 1; i < n; ++i)
            nei[host[i]].insert(i);
        auto p = SolveTree(0, a);
        return max(p.first, p.second);
    }
    if (count(prot + 1, prot + n, MY) == n - 1)
        return accumulate(a, a + n, 0);
    if (count(prot + 1, prot + n, WE) == n - 1)
        return *max_element(a, a + n);
    if (n <= 10)
    {
        bool g[10][10];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                g[i][j] = false;
        for (int i = 1; i < n; ++i)
        {
            int j = host[i];
            if (prot[i] == ME)
                g[i][j] = g[j][i] = true;
            else
            {
                for (int k = 0; k < n; ++k)
                    if (g[j][k])
                        g[i][k] = g[k][i] = true;
                if (prot[i] == WE)
                    g[i][j] = g[j][i] = true;
            }
        }
        int ans = 0;
        for (int mask = 1; mask < (1 << n); ++mask)
        {
            bool ok = true;
            int cur = 0;
            for (int i = 0; i < n; ++i)
            {
                if (!(mask & (1 << i))) continue;
                cur += a[i];
                for (int j = i + 1; j < n; ++j) {
                    if (!(mask & (1 << j))) continue;
                    if (g[i][j])
                        ok = false;
                }
            }
            if (ok) ans = max(ans, cur);
        }
        return ans;
    }
 
    int ans = 0;
    for (int i = n - 1; i > 0; --i)
    {
        if (prot[i] == ME) {
            ans += a[i];
            a[host[i]] = max(a[host[i]] - a[i], 0);
        }
        else if (prot[i] == MY)
            a[host[i]] += a[i];
      	else
         	a[host[i]] = max(a[host[i]], a[i]);
    }
    return ans + a[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