Submission #883140

#	Time	Username	Problem	Language	Result	Execution time	Memory
883140		AkibAzmain	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	176 ms	24196 KiB

supertrees

#include <bits/stdc++.h>
using namespace std;
#include "supertrees.h"
#include <vector>

int construct(std::vector<std::vector<int>> p) {
  int n = p.size();
  std::vector<std::vector<int>> ans (n, vector < int > (n));
  vector < array < bool, 3 > > pt (n);
  vector < pair < int, int > > dsu (n);
  for (int i = 0; i < n; ++i) dsu[i].first = -1, dsu[i].second = 1;
  auto dsuc = [&] (int x)
  {
    while (dsu[x].first != -1) x = dsu[x].first;
    return x;
  };
  for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j)
      if (p[i][j])
        {
          if (p[i][j] == 3) return 0;
          pt[i][p[i][j]] = pt[j][p[i][j]] = true;
          int ci = dsuc (i), cj = dsuc (j);
          if (ci != cj)
            {
              if (dsu[ci].second < dsu[cj].second) swap (ci, cj);
              dsu[cj].first = ci;
              dsu[ci].second += dsu[cj].second;
            }
        }
  for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j)
      if (!p[i][j] && dsuc (i) == dsuc (j)) return 0;
  map < int, array < set < int >, 3 > > m;
  for (int i = 0; i < n; ++i)
    {
      int ci = dsuc (i);
      if (pt[i][1]) m[ci][1].insert (i);
      if (pt[i][2]) m[ci][2].insert (i);
    }
  for (auto &[xx, x] : m)
    {
      if (x[1].empty () && x[2].empty ()) continue;
      int p = -1;
      for (auto &y : x[1])
        {
          if (x[2].size () && !x[2].count (y)) return 0;
          if (p >= 0) ans[p][y] = ans[y][p] = 1;
          p = y;
        }
      if (x[2].empty ()) continue;
      if (x[2].size () - x[1].size () <= (1 + x[1].empty ())) return 0;
      int pp = p;
      for (auto &y : x[2])
        {
          if (x[1].count (y)) continue;
          if (p >= 0) ans[p][y] = ans[y][p] = 1;
          p = y;
          if (pp == -1) pp = y;
        }
      ans[p][pp] = ans[pp][p] = 1;
    }
  build (ans);
  return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:52:39: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |       if (x[2].size () - x[1].size () <= (1 + x[1].empty ())) return 0;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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