Submission #721979

#	Time	Username	Problem	Language	Result	Execution time	Memory
721979		danikoynov	Connecting Supertrees (IOI20_supertrees)	C++14	75 / 100	199 ms	30028 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;

vector < int > graph[maxn], graph2[maxn], comp;
int cap[maxn][maxn];
int used[maxn], N;
vector<std::vector<int>> answer;

void dfs2(int v)
{
    comp.push_back(v);
    used[v] = 1;
    for (int u : graph2[v])
    {
        if (!used[u])
            dfs2(u);
    }
}

void dfs(int v)
{
    comp.push_back(v);
    used[v] = 1;
    for (int u : graph[v])
    {
        if (!used[u])
            dfs(u);
    }
}

bool solve_2_component()
{
    /**for (int i = 0; i < comp.size(); i ++)
        for (int j = 0; j < comp.size(); j ++)
            if (cap[comp[i]][comp[j]] != 2)
                return false;

    if (comp.size() == 2)
        return false;*/
    if (comp.size() == 1)
        return true;
    answer[comp[0]][comp.back()] = 1;
    answer[comp.back()][comp[0]] = 1;


    for (int i = 0; i < (int)(comp.size()) - 1; i ++)
    {
        answer[comp[i]][comp[i + 1]] = 1;
        answer[comp[i + 1]][comp[i]] = 1;
    }

    /**for (int i = 0; i < comp.size(); i ++)
        for (int j = 0; j < comp.size(); j ++)
            cap[comp[i]][comp[j]] = 0;*/

    return true;

}
bool all2;
int nec[maxn];
bool solve_component()
{
    for (int i = 0; i < comp.size(); i ++)
        for (int j = 0; j < comp.size(); j ++)
            if (cap[comp[i]][comp[j]] == 0 || (!all2 && cap[comp[i]][comp[j]] == 2))
                return false;
    memset(nec, 0, sizeof(nec));
    for (int v : comp)
        nec[v] = 1;
    if (comp.size() != 1 && all2)
    {
        if (cap[comp[0]][comp[1]] == 2)
        {
            if (comp.size() == 2)
                return false;
            answer[comp[0]][comp.back()] = 1;
            answer[comp.back()][comp[0]] = 1;
        }
    }

    for (int i = 0; i < (int)(comp.size()) - 1; i ++)
    {
        answer[comp[i]][comp[i + 1]] = 1;
        answer[comp[i + 1]][comp[i]] = 1;
    }

    for (int i = 1; i < comp.size(); i ++)
        for (int j = 0; j < N; j ++)
        {
            if (cap[comp[i]][j] == 2)
            {
                cap[comp[i]][j] = 0;
                cap[j][comp[i]] = 0;
            }


        }

    return true;

}
int construct(std::vector<std::vector<int>> p)
{
    int n = p.size();
    N = n;
    all2 = true;
    for (int i = 0; i < n; i++)
    {
        std::vector<int> row;
        row.resize(n, 0);
        answer.push_back(row);
    }

    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
        {
            if (p[i][j] == 1 && i != j)
                all2 = false;
            cap[i][j] = p[i][j];
        }



    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
        {
            if (i != j && (cap[i][j] == 1 || (cap[i][j] == 2 && all2)))
                graph[i].push_back(j);
        }

    for (int i = 0; i < n; i ++)
    {
        if (!used[i])
        {
            comp.clear();
            dfs(i);
            bool is_fine = solve_component();
            if (!is_fine)
                return 0;
        }
    }
    if (!all2)
    {

        memset(used, 0, sizeof(used));
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < n; j ++)
            {
                if (i != j && cap[i][j] == 2)
                    graph2[i].push_back(j);
            }

        for (int i = 0; i < n; i ++)
        {
            if (!used[i])
            {
                comp.clear();
                dfs2(i);
                bool is_fine = solve_2_component();
                if (!is_fine)
                    return false;
            }
        }
    }
    build(answer);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'bool solve_component()':
supertrees.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < comp.size(); i ++)
      |                     ~~^~~~~~~~~~~~~
supertrees.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int j = 0; j < comp.size(); j ++)
      |                         ~~^~~~~~~~~~~~~
supertrees.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 1; i < comp.size(); i ++)
      |                     ~~^~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4