Submission #883151

#	Time	Username	Problem	Language	Result	Execution time	Memory
883151		AkibAzmain	Connecting Supertrees (IOI20_supertrees)	C++17	19 / 100	163 ms	23588 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);
  set < int > r;
  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;
          if (p[i][j] == 1 && !r.count (i) && !r.count (j))
            ans[i][j] = 1, ans[j][i] = 1, r.insert (j);
          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;
      if (x[2].empty ())
        {
          int pr = -1;
          for (auto &y : x[1])
            {
              if (x[2].size () && !x[2].count (y)) return 0;
              if (pr >= 0) ans[pr][y] = ans[y][pr] = 1;
              pr = y;
            }
        }
      if (x[2].size () <= 2) return 0;
      int pr = *prev (x[2].end ());
      for (auto &y : x[2])
        {
          if (r.count (y)) continue;
          ans[pr][y] = ans[y][pr] = 1;
          pr = y;
          for (int i = 0; i < n; ++i)
            if (i != y && x[1].count (i) && p[y][i] == 1)
              ans[i][y] = ans[y][i] = 1;
        }
    }
  build (ans);
  return 1;
}

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