Submission #952779

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

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll mxN = 1e6 + 5;
using namespace std;

static int n;
static std::vector<std::vector<int>> p;
static std::vector<std::vector<int>> b;
static bool called = false;

static void check(bool cond, std::string message) {
    if (!cond) {
        printf("%s\n", message.c_str());
        fclose(stdout);
        exit(0);
    }
}

void build(std::vector<std::vector<int>> _b) {
    check(!called, "build is called more than once");
    called = true;
    check((int)_b.size() == n, "Invalid number of rows in b");
    for (int i = 0; i < n; i++) {
        check((int)_b[i].size() == n, "Invalid number of columns in b");
    }
    b = _b;
}
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;
}

int main() {
    assert(scanf("%d", &n) == 1);
    
    p.resize(n);
    for (int i = 0; i < n; i++) {
        p[i].resize(n);
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            assert(scanf("%d", &p[i][j]) == 1);
        }
    }
    fclose(stdin);

    int possible = construct(p);

    check(possible == 0 || possible == 1, "Invalid return value of construct");
    if (possible == 1) {
        check(called, "construct returned 1 without calling build");
    } else {
        check(!called, "construct called build but returned 0");
    }

    printf("%d\n", possible);
    if (possible == 1) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j) {
                    printf(" ");
                }
                printf("%d", b[i][j]);
            }
            printf("\n");
        }
    }
    fclose(stdout);
}

Compilation message

/usr/bin/ld: /tmp/ccqZI10i.o: in function `build(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)':
grader.cpp:(.text+0x260): multiple definition of `build(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)'; /tmp/cc8rfWsl.o:supertrees.cpp:(.text+0x4b0): first defined here
/usr/bin/ld: /tmp/ccqZI10i.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc8rfWsl.o:supertrees.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status