Submission #303548

#	Time	Username	Problem	Language	Result	Execution time	Memory
303548		Haunted_Cpp	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	269 ms	26232 KiB

supertrees

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

class DisjointSet {
private:
  vector<int> par, sz;
public:
  DisjointSet(int n) {
    par = sz = vector<int>(n);
    for (int i = 0; i < n; i++) {
      par[i] = i;
      sz[i] = 1;
    }
  }
  int root(int x) {
    if (x == par[x]) {
      return x;
    }
    return par[x] = root(par[x]);
  }
  void join(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) {
      return;
    }
    if (sz[a] < sz[b]) {
      swap(a, b);
    }
    sz[a] += sz[b];
    par[b] = a;
  }
  bool is_connected(int a, int b) {
    return root(a) == root(b);
  }
};

const int MAX_N = 1e3 + 5;

vector<vector<int>> g(MAX_N);
vector<int> cnt_two(MAX_N);
bitset<MAX_N> vis;

int construct(vector<vector<int>> mat) {
  
  const int n = (int) mat.size();
  
  DisjointSet DSU(n);
  vector<vector<int>> ans(n, vector<int>(n));
  
  for (int i = 0; i < n; i++) {
    int cnt = 0;
    for (int j = 0; j < n; j++) {
      if (i == j) {
        continue;
      }
      if (mat[i][j] == 3) {
        return 0;
      }
      cnt += (mat[i][j] == 2);
      if (mat[i][j] == 1) {
        g[i].emplace_back(j);
      }
      if (mat[i][j] > 0) {
        DSU.join(i, j);
      }
    }
    cnt_two[i] = cnt;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (mat[i][j] == 0 && DSU.is_connected(i, j)) {
        return 0;
      }
    }
  }
  vector<vector<int>> root(MAX_N);
  for (int i = 0; i < n; i++) {
    root[DSU.root(i)].emplace_back(i);
  }
  auto add_edge = [&](int st, int et) {
    if (st == et) {
      return;
    }
    ans[st][et] = ans[et][st] = 1;
  };
  auto build_cycle = [&](const vector<int> &arr) {
    for (int i = 1; i < (int) arr.size(); i++) {
      add_edge(arr[i], arr[i - 1]);
    }
    add_edge(arr.front(), arr.back());
  };
  vis.reset();
  for (auto to : root) {
    if (to.empty()) {
      continue;
    }
    const int sz = (int) to.size();
    vector<int> main_cycle;
    int is_main = 0;
    for (auto cur : to) {
      if (cnt_two[cur] == sz - 1) {
        ++is_main;
        main_cycle.emplace_back(cur);
      } else {
        if (vis[cur]) {
          continue;
        }
        main_cycle.emplace_back(cur);
        vis[cur] = true;
        vector<int> chain = {cur};
        for (auto add : g[cur]) {
          assert(vis[add] == false);
          vis[add] = true;
          add_edge(cur, add);
        }
      }
    }
    if (main_cycle.size() == 2) {
      return 0;
    }
    build_cycle(main_cycle);
  }
  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