Submission #319959

#	Time	Username	Problem	Language	Result	Execution time	Memory
319959		eriksuenderhauf	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	283 ms	24420 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int par[1005], inTree[1005];
vector<int> cyc[1005], tree[1005];

int qry(int x) { return x == par[x] ? x : par[x] = qry(par[x]); }
void join(int x, int y) { par[qry(x)] = qry(y); }

int construct(vector<vector<int>> p) {
  auto check_connectivity = [&](int n) {
    iota(par, par+n, 0);
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (p[i][j] != 0)
          join(i, j);
    for (int i = 0; i < n; i++)
      for (int j = i+1; j < n; j++)
        if (p[i][j] == 0 && qry(i) == qry(j))
          return 0;
    return 1;
  };
  auto connect = [&](int n, int t) {
    iota(par, par+n, 0);
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (p[i][j] == t)
          join(i, j);
  };
  int n = p.size();
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (p[i][j] > 2 || p[i][j] != p[j][i])
        return 0;
  if (!check_connectivity(n))
    return 0;
  connect(n, 2);
  for (int i = 0; i < n; i++)
    cyc[qry(i)].push_back(i);
  connect(n, 1);
  for (int i = 0; i < n; i++)
    tree[qry(i)].push_back(i);
  vector<vector<int>> ans(n, vector<int>(n, 0));
  for (int i = 0; i < n; i++) {
    if (int(tree[i].size()) <= 1)
      continue;
    int l = -1;
    for (int j: tree[i]) {
      for (int k: tree[i])
        if (p[j][k] != 1)
          return 0;
      if (l != -1)
        ans[l][j] = ans[j][l] = 1;
      l = j, inTree[j] = 1;
    }
  }
  for (int i = 0; i < n; i++) {
    if (int(cyc[i].size()) <= 1)
      continue;
    vector<int> nx;
    for (int j: cyc[i]) {
      if (!inTree[j])
        nx.push_back(j);
      else if (qry(j) == j)
        nx.push_back(j);
    }
    if (int(nx.size()) <= 2)
      return 0;
    int l = -1;
    for (int j: nx) {
      if (l != -1)
        ans[l][j] = ans[j][l] = 1;
      l = j;
    }
    ans[l][nx[0]] = ans[nx[0]][l] = 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