Submission #883116

#	Time	Username	Problem	Language	Result	Execution time	Memory
883116		AkibAzmain	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	159 ms	22612 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, 4 > > pt (n);
  vector < pair < int, int > > dsu (n);
  for (int i = 0; i < n; ++i) dsu[i].first = -1, dsu[i].second = 1;
  for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j)
      if (p[i][j])
        {
          pt[i][p[i][j]] = true;
          pt[j][p[i][j]] = true;
          int ci = i, cj = j;
          while (dsu[ci].first != -1) ci = dsu[ci].first;
          while (dsu[cj].first != -1) cj = dsu[cj].first;
          if (ci != cj)
            {
              if (dsu[ci].second < dsu[cj].second) swap (ci, cj);
              dsu[cj].first = ci;
              dsu[ci].second += dsu[cj].second;
            }
        }
  map < int, array < set < int >, 4 > > m;
  for (int i = 0; i < n; ++i)
    {
      int ci = i;
      while (dsu[ci].first != -1) ci = dsu[ci].first;
      for (int j = 0; j < 4; ++j) if (pt[i][j]) m[ci][j].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) 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;
}

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