Submission #697846

#	Time	Username	Problem	Language	Result	Execution time	Memory
697846		boris_mihov	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	176 ms	22908 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 < stick.size() ; ++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 < stick.size() ; ++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;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:65:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for (int j = 1 ; j < stick.size() ; ++j)
      |                              ~~^~~~~~~~~~~~~~
supertrees.cpp:78:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int j = 1 ; j < stick.size() ; ++j)
      |                      ~~^~~~~~~~~~~~~~

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