Submission #281722

#	Time	Username	Problem	Language	Result	Execution time	Memory
281722		SamAnd	Friend (IOI14_friend)	C++17	46 / 100	270 ms	65540 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;

int n;
int conf[N];
vector<int> g[N];

int dp[N][2];
void dfs(int x, int p)
{
    dp[x][1] = conf[x];
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        dfs(h, x);
        dp[x][0] += max(dp[h][0], dp[h][1]);
        dp[x][1] += dp[h][0];
    }
}

int q1, q2;
bool c[N];
void dfs1(int x, int gg)
{
    c[x] = true;
    if (gg == 1)
        ++q1;
    else
        ++q2;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (!c[h])
            dfs1(h, 3 - gg);
    }
}

int findSample(int n, int confidence[], int host[], int protocol[])
{
    ::n = n;

    for (int i = 0; i < n; ++i)
        conf[i] = confidence[i];

    for (int i = 1; i < n; ++i)
    {
        if (protocol[i] == 0)
        {
            g[host[i]].push_back(i);
            g[i].push_back(host[i]);
        }
        else if (protocol[i] == 1)
        {
            for (int j = 0; j < g[host[i]].size(); ++j)
            {
                int h = g[host[i]][j];
                g[h].push_back(i);
                g[i].push_back(h);
            }
        }
        else
        {
            for (int j = 0; j < g[host[i]].size(); ++j)
            {
                int h = g[host[i]][j];
                g[h].push_back(i);
                g[i].push_back(h);
            }
            g[host[i]].push_back(i);
            g[i].push_back(host[i]);
        }
    }

    for (int i = 0; i < n; ++i)
        sort(g[i].begin(), g[i].end());

    bool z = true;
    for (int i = 1; i < n; ++i)
    {
        if (protocol[i] != protocol[1])
        {
            z = false;
            break;
        }
    }

    if (z)
    {
        if (protocol[1] == 1)
        {
            int ans = 0;
            for (int i = 0; i < n; ++i)
                ans += confidence[i];
            return ans;
        }
        if (protocol[1] == 2)
        {
            int ans = 0;
            for (int i = 0; i < n; ++i)
                ans = max(ans, confidence[i]);
            return ans;
        }
        dfs(0, 0);
        return max(dp[0][0], dp[0][1]);
    }

    if (n > 10)
    {
        int ans = 0;
        for (int x = 0; x < n; ++x)
        {
            if (c[x])
                continue;
            q1 = q2 = 0;
            dfs1(x, 1);
            ans += max(q1, q2);
        }
        return ans;
    }

    int ans = 0;
    for (int x = 0; x < (1 << n); ++x)
    {
        int yans = 0;
        bool z = true;
        for (int i = 0; i < n; ++i)
        {
            if (!(x & (1 << i)))
                continue;
            yans += confidence[i];
            for (int j = 0; j < n; ++j)
            {
                if (!(x & (1 << j)))
                    continue;
                if (binary_search(g[i].begin(), g[i].end(), j))
                {
                    z = false;
                    break;
                }
            }
            if (!z)
                break;
        }
        if (z)
            ans = max(ans, yans);
    }
    return ans;
}

Compilation message (stderr)

friend.cpp: In function 'void dfs(int, int)':
friend.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
friend.cpp: In function 'void dfs1(int, int)':
friend.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:58:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for (int j = 0; j < g[host[i]].size(); ++j)
      |                             ~~^~~~~~~~~~~~~~~~~~~
friend.cpp:67:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             for (int j = 0; j < g[host[i]].size(); ++j)
      |                             ~~^~~~~~~~~~~~~~~~~~~

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