oj.uz

Submission #292970

# Submission time Handle Problem Language Result Execution time Memory
292970 2020-09-07T15:11:16 Z AaronNaidu Friend (IOI14_friend) C++14
46 / 100
 36 ms 2548 KB 
#include <bits/stdc++.h>
using namespace std;

int matrix[11][11];
int subTrees[2000][2];
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 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 (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

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Incorrect 1 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Incorrect 36 ms 2548 KB Output isn't correct
13 Halted 0 ms 0 KB -