Submission #1212861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212861		kunzaZa183	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	141 ms	22336 KiB

supertrees

#include "supertrees.h"

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

int construct(vector<vector<int>> p) {
  for (auto &a : p)
    for (auto &b : a)
      if (b == 3) return 0;

  int n = p.size();
  vector<vector<int>> edge(n, vector<int>(n, 0));

  vector<int> c1(n), c2(n);
  iota(c1.begin(), c1.end(), 0ll);
  iota(c2.begin(), c2.end(), 0ll);

  function<int(vector<int> &, int)> par = [&](vector<int> &vi, int cur) {
    if (vi[cur] == cur) return vi[cur];

    return vi[cur] = par(vi, vi[cur]);
  };

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (p[i][j] > 0) {
        int x = par(c1, i), y = par(c1, j);

        c1[x] = y;
      }
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (par(c1, i) == par(c1, j) && p[i][j] == 0) {
        return 0;
      }
      if (p[i][j] > 0 && par(c1, i) != par(c1, j)) {
        return 0;
      }
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (p[i][j] == 1) {
        int x = par(c2, i), y = par(c2, j);

        c2[x] = y;
      }
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (par(c2, i) == par(c2, j) && p[i][j] != 1) {
        return 0;
      }
      if (par(c2, i) != par(c2, j) && p[i][j] == 1) {
        return 0;
      }
    }
  }

  map<int, map<int, vector<int>>> mimii;
  for (int i = 0; i < n; i++) mimii[c1[i]][c2[i]].push_back(i);

  vector<pair<int, int>> elist;
  for (auto &a : mimii) {
    vector<int> loop;
    for (auto &b : a.second) {
      loop.push_back(b.second[0]);

      for (int i = 0; i + 1 < b.second.size(); i++)
        elist.emplace_back(b.second[i], b.second[i + 1]);
    }

    if (loop.size() == 2) return 0;

    for (int i = 0; i + 1 < loop.size(); i++)
      elist.emplace_back(loop[i], loop[i + 1]);
    if (loop.size() > 1) elist.emplace_back(loop[0], loop.back());
  }

  // for (int i = 0; i < n; i++) edge[i][i] = 1;

  for (auto [a, b] : elist) {
    edge[a][b] = edge[b][a] = 1;
  }
  build(edge);
  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