Submission #697837

#	Time	Username	Problem	Language	Result	Execution time	Memory
697837		boris_mihov	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	204 ms	24052 KiB

supertrees

#include "supertrees.h"
#include <vector>

typedef long long llong;
const int MAXN = 1000 + 10;
const int INF  = 1e9;

bool used[MAXN];
std::vector <std::vector <int>> b;

inline void addEdge(int x, int y)
{
    b[x][y] = 1;
    b[y][x] = 1;
}

int construct(std::vector <std::vector <int>> p) 
{
	int n = p.size();
    b.resize(n);

	for (int i = 0 ; i < n ; ++i)
    {
        b[i].resize(n, 0);
        for (int j = 0 ; j < n ; ++j)
        {
            if (p[i][j] == 3)
            {
                return 0;
            }
        }
    }

    for (int i = 0 ; i < n ; ++i)
    {
        if (used[i]) 
        {
            continue;
        }

        used[i] = true;
        std::vector <int> by[3];
        by[1].push_back(i);
        by[2].push_back(i);

        for (int j = 0 ; j < n ; ++j)
        {
            if (p[i][j] == 0 || i == j) continue;
            if (used[j]) return 0;

            for (int k = 0 ; k < n ; ++k)
            {
                if (i == k || j == k) continue;
                if (((p[i][j] == 2 && p[i][k] == 1) ? 2 : p[i][k]) != p[j][k]) return 0;
            }

            by[p[i][j]].push_back(j);
            used[j] = true;
        }

        if (by[2].size() == 2) return 0;
        for (int i = 1 ; i < (int)by[1].size() ; ++i)
        {
            addEdge(by[1][i - 1], by[1][i]);
        }

        for (int i = 1 ; i < (int)by[2].size() ; ++i)
        {
            addEdge(by[2][i - 1], by[2][i]);
        }

        if (by[2].size() >= 3)
        {
            addEdge(i, by[2].back());
        }
    }

    build(b);
	return 1;
}

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