Submission #313159

#	Time	Username	Problem	Language	Result	Execution time	Memory
313159		wasyl	Connecting Supertrees (IOI20_supertrees)	C++17	46 / 100	247 ms	22264 KiB

supertrees

#include "supertrees.h"
#include <vector>
using namespace std;

int construct(std::vector<std::vector<int>> p) {
    //int n = p.size();
    //std::vector<std::vector<int>> answer;
    //for (int i = 0; i < n; i++) {
    //	std::vector<int> row;
    //	row.resize(n);
    //	answer.push_back(row);
    //}
    //build(answer);
    //return 1;


    int n = p.size();
    vector< vector< int > > ans(n, vector< int >(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (p[i][j] == 3)
                return 0;

    vector< int > siv(n, false);

    vector< int > vis(n, false);
    for (int i = 0; i < n; ++i)
        if (not vis[i])
        {
            vector< int > sub;
            for (int j = 0; j < n; ++j)
                if (p[i][j] and not vis[j])
                    sub.push_back(j);
                else if (p[i][j] and vis[j]) return 0;

            for (int a : sub)
                for (int b : sub)
                    if (not p[a][b])
                        return 0;

            for (int a : sub)
                vis[a] = true;
            
                
            vector< vector< int > > div;
            for (int a : sub)
                if (not siv[a])
                {
                    div.push_back(vector< int >());
                    for (int b : sub)
                        if (p[a][b] == 1 and not siv[b])
                            div.back().push_back(b);
                        else if (p[a][b] == 1 and siv[b]) return 0;

                    for (int a : div.back())
                        for (int b : div.back())
                            if (p[a][b] != 1)
                                return 0;

                    for (int a : div.back())
                        siv[a] = true;
                }

            for (int i = 1; i < div.size(); ++i)
                ans[div[i - 1][0]][div[i][0]] = ans[div[i][0]][div[i - 1][0]] = 1;
                
            if (div.size() > 1)
                ans[div.back()[0]][div.front()[0]] = ans[div.front()[0]][div.back()[0]] = 1;

            for (const auto& vv : div)
                for (int i = 1; i < vv.size(); ++i)
                    ans[vv[i]][vv[i - 1]] = ans[vv[i - 1]][vv[i]] = 1;
        }

    build(ans);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:64:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for (int i = 1; i < div.size(); ++i)
      |                             ~~^~~~~~~~~~~~
supertrees.cpp:71:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |                 for (int i = 1; i < vv.size(); ++i)
      |                                 ~~^~~~~~~~~~~

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