Submission #301723

#	Time	Username	Problem	Language	Result	Execution time	Memory
301723		rama_pang	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	272 ms	22368 KiB

supertrees

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

class DisjointSet {
 public:
  vector<int> p;
  DisjointSet() {}
  DisjointSet(int sz) : p(sz) {
    iota(begin(p), end(p), 0);
  }
  int Find(int x) {
    return p[x] == x ? x : p[x] = Find(p[x]);
  }
  int Unite(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) {
      return 0;
    }
    p[x] = y;
    return 1;
  }
  bool SameSet(int x, int y) {
    return Find(x) == Find(y);
  }
  bool IsRoot(int x) {
    return Find(x) == x;
  }
};

int construct(vector<vector<int>> p) {
  int n = (int) p.size();
  vector<vector<int>> ans(n, vector<int>(n, 0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (p[i][j] == 3) {
        return 0;
      }
    }
  }
  DisjointSet D(n), T(n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (p[i][j] > 0) {
        D.Unite(i, j);
      }
    }
  }
  vector<vector<int>> comps(n);
  vector<vector<int>> trees(n);
  for (int i = 0; i < n; i++) {
    comps[D.Find(i)].emplace_back(i);
  }
  for (const auto &c : comps) {
    if (c.empty()) {
      continue;
    }
    for (auto i : c) {
      for (auto j : c) {
        if (p[i][j] == 0) {
          return 0;
        }
      }
    }
    for (auto i : c) {
      for (auto j : c) {
        if (p[i][j] == 1) {
          T.Unite(i, j);
        }
      }
    }
    for (auto i : c) {
      trees[T.Find(i)].emplace_back(i);
    }
    vector<int> roots;
    for (auto r : c) {
      if (T.IsRoot(r)) {
        roots.emplace_back(r);
        for (auto i : trees[r]) {
          for (auto j : trees[r]) {
            if (p[i][j] == 2) {
              return 0;
            }
          }
        }
        for (int i = 0; i + 1 < (int) trees[r].size(); i++) {
          ans[trees[r][i]][trees[r][i + 1]] = 1;
          ans[trees[r][i + 1]][trees[r][i]] = 1;
        }
      }
    }
    if (roots.size() == 1) {
      continue;
    }
    if (roots.size() == 2) {
      return 0;
    }
    roots.emplace_back(roots.front());
    for (int i = 0; i + 1 < (int) roots.size(); i++) {
      ans[roots[i]][roots[i + 1]] = 1;
      ans[roots[i + 1]][roots[i]] = 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