Submission #697848

#	Time	Username	Problem	Language	Result	Execution time	Memory
697848		boris_mihov	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	211 ms	23008 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;

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::fill(inComp, inComp + n, -1);
    for (int i = 0 ; i < n ; ++i)
    {
        if (inComp[i] != -1) continue;
        std::vector <int> stick;
        stick.push_back(i);
        inComp[i] = i;

        for (int j = 0 ; j < n ; ++j)
        {
            if (i == j || p[i][j] != 1) continue;
            stick.push_back(j);
            inComp[j] = i;

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

        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;
        
            for (int k = 0 ; k < n ; ++k)
            {
                if (k == inComp[i] || k == inComp[j]) continue;
                if (inComp[k] == inComp[i])
                {
                    if (p[k][inComp[j]] != 2) return 0;
                    continue;
                }            

                if (inComp[k] == inComp[j])
                {
                    if (p[k][inComp[i]] != 2) return 0;
                    continue;
                } 

                if (p[inComp[i]][k] != p[inComp[j]][k]) return 0;      
            }
        }

        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:60:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int j = 1 ; j < stick.size() ; ++j)
      |                          ~~^~~~~~~~~~~~~~

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