Submission #1071973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071973		andrei_iorgulescu	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	148 ms	28088 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
#warning That's not FB, that's my FB

using namespace std;

int n;
vector<vector<int>> cc, cc2;
vector<int> cur;
vector<bool> viz;
vector<vector<int>> p;

void dfs(int nod)
{
    viz[nod] = true;
    cur.push_back(nod);
    for (int i = 0; i < n; i++)
    {
        if (i != nod and !viz[i] and p[nod][i] != 0)
            dfs(i);
    }
}

void dfs2(int nod)
{
    viz[nod] = true;
    cur.push_back(nod);
    for (int i = 0; i < n; i++)
    {
        if (i != nod and !viz[i] and p[nod][i] == 1)
            dfs2(i);
    }
}

int construct(vector<vector<int>> P)
{
    p = P;
    n = p.size();
    viz.resize(n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (p[i][j] == 3)
                return 0;
    for (int i = 0; i < n; i++)
    {
        if (!viz[i])
        {
            cur.clear();
            dfs(i);
            cc.push_back(cur);
        }
    }
    for (auto it : cc)
    {
        for (auto itt : it)
            for (auto ittt : it)
                if (p[itt][ittt] == 0)
                    return 0;
    }
    vector<pair<int,int>> edges;
    for (int i = 0; i < n; i++)
        viz[i] = false;
    for (auto v : cc)
    {
        cc2.clear();
        for (auto it : v)
        {
            if (!viz[it])
            {
                cur.clear();
                dfs2(it);
                cc2.push_back(cur);
            }
        }
        for (auto vv : cc2)
        {
            /*for (auto it : vv)
                cout << it << ' ';
            cout << endl;*/
            for (auto it1 : vv)
            {
                for (auto it2 : vv)
                    if (p[it1][it2] != 1)
                        return 0;
            }
        }
        if (cc2.size() == 2)
            return 0;
        if (cc2.size() == 1)
        {
            for (int i = 0; i + 1 < v.size(); i++)
                edges.push_back({v[i], v[i + 1]});
        }
        else if (cc2.size() >= 3)
        {
            for (auto vv : cc2)
            {
                for (int i = 0; i + 1 < vv.size(); i++)
                    edges.push_back({vv[i], vv[i + 1]});
            }
            for (int i = 0; i < cc2.size(); i++)
                edges.push_back({cc2[i][0], cc2[(i + 1) % (int)cc2.size()][0]});
        }
    }
    vector<vector<int>> bld(n);
    for (int i = 0; i < n; i++)
        bld[i].resize(n);
    for (auto it : edges)
        bld[it.first][it.second] = bld[it.second][it.first] = 1;
    build(bld);
    return 1;
}

Compilation message (stderr)

supertrees.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:91:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             for (int i = 0; i + 1 < v.size(); i++)
      |                             ~~~~~~^~~~~~~~~~
supertrees.cpp:98:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |                 for (int i = 0; i + 1 < vv.size(); i++)
      |                                 ~~~~~~^~~~~~~~~~~
supertrees.cpp:101:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |             for (int i = 0; i < cc2.size(); i++)
      |                             ~~^~~~~~~~~~~~

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