Submission #390483

#	Time	Username	Problem	Language	Result	Execution time	Memory
390483		AlexPop28	Connecting Supertrees (IOI20_supertrees)	C++14	96 / 100	294 ms	24268 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <iostream>
#include <cassert>

using namespace std;

struct DSU {
  int n;
  vector<int> dad;
  vector<vector<int>> t;
  DSU(int n_) : n(n_), dad(n, -1), t(n) {
    for (int i = 0; i < n; ++i) {
      t[i] = {i};
    }
  }

  int Find(int x) {
    if (dad[x] == -1) return x;
    return dad[x] = Find(dad[x]);
  }

  bool Union(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) return false;
    if (t[x].size() < t[y].size()) swap(x, y);
    t[x].insert(t[x].end(), t[y].begin(), t[y].end());
    dad[y] = x;
    return true;
  }

  bool Connected(int x, int y) {
    return Find(x) == Find(y);
  }
};

int construct(vector<vector<int>> p) {
  int n = p.size();
  vector<vector<int>> ans(n, vector<int>(n));

  auto AddEdge = [&](int a, int b) {
    if (a != b) ans[a][b] = ans[b][a] = 1;
  };

  DSU dsu(n);
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (p[i][j] == 1) {
        if (dsu.Union(i, j)) {
          AddEdge(i, j);
        }
      }
    }
  }

  vector<int> roots;
  for (int i = 0; i < n; ++i) {
    if (dsu.Find(i) == i) roots.emplace_back(i);
  }

  for (int node : roots) {
    for (int i = 0; i < (int)dsu.t[node].size(); ++i) {
      int x = dsu.t[node][i];
      for (int j = i + 1; j < (int)dsu.t[node].size(); ++j) {
        int y = dsu.t[node][j];
        if (p[x][y] != 1) return 0;
      }
    }
  }

  DSU dsu_roots(n);
  for (int i = 0; i < (int)roots.size(); ++i) {
    int x = roots[i];
    for (int j = i + 1; j < (int)roots.size(); ++j) {
      int y = roots[j];
      if (p[x][y] == 2) {
        dsu_roots.Union(x, y);
      }
    }
  }
  
  for (int root : roots) {
    if (dsu_roots.Find(root) != root) continue;

    auto &v = dsu_roots.t[root];
    if ((int)v.size() == 1) continue;
    if ((int)v.size() == 2) return 0;

    for (int i = 0; i < (int)v.size(); ++i) {
      int j = i + 1;
      if (j == (int)v.size()) j = 0;
      AddEdge(v[i], v[j]);
    }
  }

  bool ret = true;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (dsu.Connected(i, j)) {
        ret &= p[i][j] == 1;
      } else {
        ret &= p[i][j] != 1;
      }
      if (dsu.Find(i) != dsu.Find(j) &&
          dsu_roots.Connected(dsu.Find(i), dsu.Find(j))) {
        ret &= p[i][j] == 2;
      } else {
        ret &= p[i][j] != 2;
      }
    }
  }
  
  if (!ret) return 0;

  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: 0 / 4