Submission #300744

#	Time	Username	Problem	Language	Result	Execution time	Memory
300744		IgorI	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	303 ms	22264 KiB

supertrees

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)

void build(vector<vector<int> > b) ;

void build(vector<vector<int> > b) ;

int Root(int x, vector<int> &root)
{
    if (x == root[x]) return x;
    return root[x] = Root(root[x], root);
}

void Merge(int v, int u, vector<int> &root, vector<int> &sz)
{
    v = Root(v, root), u = Root(u, root);
    if (v == u) return;
    if (sz[v] > sz[u]) swap(v, u);
    sz[u] += sz[v];
    root[v] = u;
}

int construct(vector<vector<int> > p)
{
    int n = p.size();
    vector<int> root(n), sz(n);
    for (int i = 0; i < n; i++) root[i] = i, sz[i] = 1;
    int t = 0;
    forn(i, n)
    {
        forn(j, n)
        {
            if (p[i][j] == 3)
            {
                return 0;
            }
            if (p[i][j])
            {
                Merge(i, j, root, sz);
            }
        }
    }
    forn(i, n)
    {
        forn(j, n)
        {
            if (Root(i, root) == Root(j, root) && p[i][j] == 0)
            {
                return 0;
            }
        }
    }
    vector<vector<int> > b(n, vector<int>(n));
    forn(i, n)
    {
        vector<int> L;
        forn(j, n)
        {
            if (Root(j, root) == i)
            {
                L.push_back(j);
            }
        }
        vector<int> root2(L.size()), sz2(L.size());
        iota(root2.begin(), root2.end(), 0);
        fill(sz2.begin(), sz2.end(), 1);
        for (int a = 0; a < L.size(); a++)
        {
            for (int b = 0; b < L.size(); b++)
            {
                if (p[L[a]][L[b]] == 1)
                {
                    Merge(a, b, root2, sz2);
                }
            }
        }
        for (int a = 0; a < L.size(); a++)
        {
            for (int b = 0; b < L.size(); b++)
            {
                if (p[L[a]][L[b]] == 2 && Root(a, root2) == Root(b, root2))
                    return 0;
            }
        }
        vector<vector<int> > z(L.size());
        for (int a = 0; a < L.size(); a++)
        {
            z[Root(a, root2)].push_back(L[a]);
        }
        vector<int> q;
        for (int j = 0; j < z.size(); j++)
        {
            if (z[j].size()) q.push_back(z[j][0]);
            for (int e = 0; e + 1 < z[j].size(); e++)
            {
                b[z[j][e]][z[j][e + 1]] = 1;
                b[z[j][e + 1]][z[j][e]] = 1;
            }
        }
        if (q.size() == 2)
        {
            return 0;
        }
        if (q.size() > 2)
        for (int i = 0; i < q.size(); i++)
        {
            b[q[i]][q[(i + 1) % q.size()]] = 1;
            b[q[(i + 1) % q.size()]][q[i]] = 1;
        }
    }
    build(b);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:5:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
      |                             ^
supertrees.cpp:32:5: note: in expansion of macro 'forn'
   32 |     forn(i, n)
      |     ^~~~
supertrees.cpp:5:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    5 | #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
      |                             ^
supertrees.cpp:34:9: note: in expansion of macro 'forn'
   34 |         forn(j, n)
      |         ^~~~
supertrees.cpp:5:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
      |                             ^
supertrees.cpp:46:5: note: in expansion of macro 'forn'
   46 |     forn(i, n)
      |     ^~~~
supertrees.cpp:5:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    5 | #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
      |                             ^
supertrees.cpp:48:9: note: in expansion of macro 'forn'
   48 |         forn(j, n)
      |         ^~~~
supertrees.cpp:5:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
      |                             ^
supertrees.cpp:57:5: note: in expansion of macro 'forn'
   57 |     forn(i, n)
      |     ^~~~
supertrees.cpp:5:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    5 | #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
      |                             ^
supertrees.cpp:60:9: note: in expansion of macro 'forn'
   60 |         forn(j, n)
      |         ^~~~
supertrees.cpp:70:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (int a = 0; a < L.size(); a++)
      |                         ~~^~~~~~~~~~
supertrees.cpp:72:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for (int b = 0; b < L.size(); b++)
      |                             ~~^~~~~~~~~~
supertrees.cpp:80:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for (int a = 0; a < L.size(); a++)
      |                         ~~^~~~~~~~~~
supertrees.cpp:82:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             for (int b = 0; b < L.size(); b++)
      |                             ~~^~~~~~~~~~
supertrees.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int a = 0; a < L.size(); a++)
      |                         ~~^~~~~~~~~~
supertrees.cpp:94:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for (int j = 0; j < z.size(); j++)
      |                         ~~^~~~~~~~~~
supertrees.cpp:97:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             for (int e = 0; e + 1 < z[j].size(); e++)
      |                             ~~~~~~^~~~~~~~~~~~~
supertrees.cpp:108:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for (int i = 0; i < q.size(); i++)
      |                         ~~^~~~~~~~~~
supertrees.cpp:31:9: warning: unused variable 't' [-Wunused-variable]
   31 |     int t = 0;
      |         ^

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