Submission #697845

#	Time	Username	Problem	Language	Result	Execution time	Memory
697845		boris_mihov	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	340 KiB

supertrees

#include "supertrees.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

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

int perm[MAXN];
bool used[MAXN];
int inComp[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;
            }
        }
    }

    std::iota(perm, perm + n, 0);
    std::sort(perm, perm + n, [&](int x, int y)
    {
        for (int i = 0 ; i < n ; ++i)
        {
            if (p[x][i] < p[y][i]) return true;
            if (p[x][i] > p[y][i]) return false;
        }

        return p[y][x] < p[x][y];
    });

    int last = 0;
    std::vector <int> stick;
    for (int i = 1 ; i < n ; ++i)
    {
        bool areEqual = (p[perm[i]][perm[last]] == 1);
        for (int j = 0 ; j < n && areEqual ; ++j)
        {
            if (perm[i] == j || perm[last] == j) continue;
            areEqual &= (p[perm[i]][j] == p[perm[last]][j]);
        }

        if (!areEqual)
        {
            for (int j = 1 ; j < n ; ++j)
            {
                addEdge(stick[j - 1], stick[j]);
            }

            stick.clear();
            last = i;
        }

        stick.push_back(perm[i]);
        inComp[perm[i]] = last;
    }

    for (int j = 1 ; j < n ; ++j)
    {
        addEdge(stick[j - 1], stick[j]);
    }

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

        std::vector <int> cycle;
        used[inComp[i]] = true;
        cycle.push_back(i);

        for (int j = 0 ; j < n ; ++j)
        {
            if (used[inComp[j]] || p[i][j] != 2) continue;
            cycle.push_back(inComp[j]);
            used[inComp[j]] = true;
        }

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

        addEdge(i, cycle.back());
    }

    build(b);
	return 1;
}

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