Submission #300711

#	Time	Username	Problem	Language	Result	Execution time	Memory
300711		IgorI	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	284 ms	22392 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) ;

const int N = 5000;
int root[N], sz[N];

int Root(int x)
{
    if (x == root[x]) return x;
    return root[x] = Root(root[x]);
}

void Merge(int v, int u)
{
    v = Root(v), u = Root(u);
    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();
    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])
            {
                Merge(i, j);
                t = max(t, p[i][j]);
            }
        }
    }
    forn(i, n)
    {
        forn(j, n)
        {
            if (p[i][j] == 0 && Root(i) == Root(j))
                return 0;
        }
    }
    vector<vector<int> > b(n, vector<int>(n));
    if (t == 0)
    {
        build(b);
        return 1;
    }
    for (int i = 0; i < n; i++)
    {
        vector<int> L;
        forn(j, n)
        {
            if (Root(j) == i) L.push_back(j);
        }
        for (int j = 0; j + 1 < L.size(); j++)
        {
            b[L[j]][L[j + 1]] = 1;
            b[L[j + 1]][L[j]] = 1;
        }
        if (t == 2)
        {
            if (L.size() == 2)
            {
                return 0;
            }
            if (L.size() > 2)
            {
                b[L[0]][L.back()] = 1;
                b[L.back()][L[0]] = 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:34:5: note: in expansion of macro 'forn'
   34 |     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:36:9: note: in expansion of macro 'forn'
   36 |         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:45:5: note: in expansion of macro 'forn'
   45 |     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:47:9: note: in expansion of macro 'forn'
   47 |         forn(j, 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:62:9: note: in expansion of macro 'forn'
   62 |         forn(j, n)
      |         ^~~~
supertrees.cpp:66:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int j = 0; j + 1 < L.size(); j++)
      |                         ~~~~~~^~~~~~~~~~

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