Submission #883159

#	Time	Username	Problem	Language	Result	Execution time	Memory
883159		AkibAzmain	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	167 ms	24148 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[2].empty ()) continue;
      if (x[2].size () <= 2) return 0;
      int pr = -1, f = -1;
      for (auto &y : x[2])
        {
          if (r.count (y)) continue;
          if (pr != -1) ans[pr][y] = ans[y][pr] = 1;
          pr = y;
          if (f == -1) f = y;
        }
      ans[pr][f] = ans[f][pr] = 1;
    }
  build (ans);
  return 1;
}

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