Submission #721939

#	Time	Username	Problem	Language	Result	Execution time	Memory
721939		danikoynov	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	225 ms	31952 KiB

supertrees

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

vector < int > graph[maxn], comp;
int cap[maxn][maxn];
int used[maxn];
vector<std::vector<int>> answer;
void dfs(int v)
{
    comp.push_back(v);
    used[v] = 1;
    for (int u : graph[v])
    {
        if (!used[u])
            dfs(u);
    }
}

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)
            return false;

    if (comp.size() != 1)
    {
        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;
    }



    return true;

}
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	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 ++)
        cap[i][j] = p[i][j];

	for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
    {
        if (i != j && p[i][j] != 0)
            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;
        }
    }
	build(answer);
	return 1;
}

Compilation message (stderr)

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

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