Submission #293006

#	Time	Username	Problem	Language	Result	Execution time	Memory
293006		AaronNaidu	Friend (IOI14_friend)	C++14	46 / 100	57 ms	2164 KiB

friend

#include <bits/stdc++.h>
using namespace std;

int matrix[11][11];
int subTrees[2000][2];
int degrees[2000];
vector<int> graph[2000];
vector<int> confs;
int globMax = 0;
int n;

int tryItOut(vector<int> v) {
    for (int i = 0; i < v.size(); i++)
    {
        for (int j = i+1; j < v.size(); j++)
        {
            if (matrix[v[i]][v[j]])
            {
                return 0;
            }
        }
    }
    int toRet = 0;
    for (int i = 0; i < v.size(); i++)
    {
        toRet += confs[v[i]];
    }
    return toRet;
}

void doStuff(int x, vector<int> v) {
    if (x == n) {
        globMax = max(globMax, tryItOut(v));
        return;
    }
    v.push_back(x);
    doStuff(x+1, v);
    v.pop_back();
    doStuff(x+1, v);
}

int sub1(int n, int confidence[], int host[], int protocol[]) {
    for (int i = 1; i < n; i++)
    {
        if (protocol[i] == 0)
        {
            matrix[i][host[i]] = 1;
            matrix[host[i]][i] = 1;
        }
        else if (protocol[i] == 1)
        {
            for (int j = 0; j < 11; j++)
            {
                if (matrix[host[i]][j] == 1)
                {
                    matrix[i][j] = 1;
                    matrix[j][i] = 1;
                }
                
            }
        }
        else
        {
            for (int j = 0; j < 11; j++)
            {
                if (matrix[host[i]][j] == 1)
                {
                    matrix[i][j] = 1;
                    matrix[j][i] = 1;
                }
            }
            matrix[i][host[i]] = 1;
            matrix[host[i]][i] = 1;
        }
    }
    vector<int> v;
    doStuff(0, v);
    return globMax;
}

int maxSubtree(int node, bool canInclude) {
    if (subTrees[node][canInclude] > 0)
    {
        return subTrees[node][canInclude];
    }
    
    if (graph[node].size() == 0)
    {
        if (canInclude)
        {
            return confs[node];
        }
        return 0;
    }
    if (!canInclude)
    {
        int totSum = 0;
        for (auto i : graph[node])
        {
            totSum += maxSubtree(i, true);
        }
        subTrees[node][canInclude] = totSum;
        return totSum;
    }
    int totSum1 = 0;
    for (auto i : graph[node])
    {
        totSum1 += maxSubtree(i, true);
    }
    int totSum2 = confs[node];
    for (auto i : graph[node])
    {
        totSum2 += maxSubtree(i, false);
    }
    int totSum = max(totSum1, totSum2);
    subTrees[node][canInclude] = totSum;
    return totSum;
}

int sub5(int N, int confidence[], int host[], int protocol[]) {
    int totDegree = 0;
    for (int i = 1; i < N; i++)
    {
        if (protocol[i] == 0)
        {
            degrees[i] = 1;
            degrees[host[i]]++;
            graph[i].push_back(host[i]);
            graph[host[i]].push_back(i);
            totDegree += 2;
        }
        if (protocol[i] == 1)
        {
            degrees[i] = degrees[host[i]];
            totDegree += 2 * degrees[host[i]];
            for (auto j : graph[host[i]])
            {
                degrees[j]++;
                graph[j].push_back(i);
                graph[i].push_back(j);
            }
        }
    }
    int toRet = N;
    while (totDegree > 0)
    {
        int maxDegree = 0;
        int maxIndex = -1;
        for (int i = 0; i < N; i++)
        {
            if (degrees[i] > maxDegree)
            {
                maxDegree = degrees[i];
                maxIndex = i;    
            }
        }
        toRet--;
        //cout << "Removing " << maxIndex << "\n";
        totDegree -= maxDegree;
        degrees[maxIndex] = 0;
        for (auto i : graph[maxIndex])
        {
            if (degrees[i] > 0)
            {
                degrees[i]--;
                totDegree--;
            }
        }
        graph[maxIndex].clear();
    }
    return toRet;
}

int findSample(int N, int confidence[], int host[], int protocol[]) {
    n = N;
    int confSum = 0;
    int confMax = 0;
    for (int i = 0; i < n; i++)
    {
        confs.push_back(confidence[i]);
        confSum += confs[i];
        confMax = max(confMax, confs[i]);
    }
    if (confMax == 1)
    {
        return sub5(n, confidence, host, protocol);
    }
    if (n <= 10)
    {
        n = N;
        return sub1(n, confidence, host, protocol);
    }
    if (protocol[1] == 1)
    {
        return confSum;
    }
    if (protocol[1] == 2)
    {
        return confMax;
    }
    for (int i = 1; i < n; i++)
    {
        graph[host[i]].push_back(i);
        //graph[i].push_back(host[i]);
    }
    return maxSubtree(0, true);
}

Compilation message (stderr)

friend.cpp: In function 'int tryItOut(std::vector<int>)':
friend.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
friend.cpp:15:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         for (int j = i+1; j < v.size(); j++)
      |                           ~~^~~~~~~~~~
friend.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~

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