Submission #952780

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
952780	2024-03-24T19:23:22 Z	emad234	Connecting Supertrees (IOI20_supertrees)	C++17	Compilation error	0 ms	0 KB

supertrees

int dsu[mxN];
int find(int x) { return dsu[x] == x ? x : dsu[x] = find(dsu[x]); }
void merge(int a, int b) { dsu[find(b)] = find(a); }
int construct(std::vector<std::vector<int>> p)
{
  vector<vector<int>> b;
  int n = p.size(), m = p.size();
  b.resize(n);
  for (int i = 0; i < n; i++)
    dsu[i] = i;
  for (int i = 0; i < n; i++)
    b[i].resize(m);
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      if (i == j)
        continue;
      if (p[i][j] == 1)
      {
        if (find(i) != find(j))
        {
          merge(i, j);
          b[i][j] = 1;
          b[j][i] = 1;
        }
      }
    }
  }
  vector<vector<int>> ty;
  vector<set<int>> v;
  v.resize(n);
  ty.resize(n);
  for (int i = 0; i < n; i++)
  {
    ty[i].resize(n);
    for (int j = 0; j < m; j++)
    {
      ty[i][j] = -1;
    }
  }
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      if (i == j)
        continue;
      if (find(i) == find(j))
      {
        if (p[i][j] != 1)
          return 0;
      }
      else
      {
        if (ty[find(i)][find(j)] != -1 && p[i][j] != ty[find(i)][find(j)])
          return 0;
        if (p[i][j] == 2)
        {
          v[find(i)].insert(find(j));
          v[find(j)].insert(find(i));
        }
        ty[find(i)][find(j)] = p[i][j];
      }
    }
  }
  vector<bool> vis(n);
  for (int i = 0; i < n; i++)
  {
    int prv = -1;
    if (vis[i])
      continue;
    if (v[i].size() == 1)
      return 0;
    v[i].insert(i);
    for (auto x : v[i])
    {
      for (int j = 0; j < n; j++)
      {
        if (x == j)
          continue;
        if (v[i].find(j) != v[i].end() && p[x][j] != 2)
          return 0;
      }
    }
    for (auto x : v[i])
    {
      vis[x] = 1;
      if (prv != -1)
      {
        b[x][prv] = 1;
        b[prv][x] = 1;
      }
      prv = x;
    }
    if (v[i].size() >= 2)
    {
      b[*v[i].begin()][*v[i].rbegin()] = 1;
      b[*v[i].rbegin()][*v[i].begin()] = 1;
    }
  }
  build(b);
  return 1;
}

Compilation message

supertrees.cpp:1:9: error: 'mxN' was not declared in this scope
    1 | int dsu[mxN];
      |         ^~~
supertrees.cpp: In function 'int find(int)':
supertrees.cpp:2:26: error: 'dsu' was not declared in this scope
    2 | int find(int x) { return dsu[x] == x ? x : dsu[x] = find(dsu[x]); }
      |                          ^~~
supertrees.cpp: In function 'void merge(int, int)':
supertrees.cpp:3:28: error: 'dsu' was not declared in this scope
    3 | void merge(int a, int b) { dsu[find(b)] = find(a); }
      |                            ^~~
supertrees.cpp: At global scope:
supertrees.cpp:4:20: error: 'vector' is not a member of 'std'
    4 | int construct(std::vector<std::vector<int>> p)
      |                    ^~~~~~
supertrees.cpp:1:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
  +++ |+#include <vector>
    1 | int dsu[mxN];
supertrees.cpp:4:32: error: 'vector' is not a member of 'std'
    4 | int construct(std::vector<std::vector<int>> p)
      |                                ^~~~~~
supertrees.cpp:4:32: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
supertrees.cpp:4:39: error: expected primary-expression before 'int'
    4 | int construct(std::vector<std::vector<int>> p)
      |                                       ^~~