Submission #1313259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313259		ayaz	Connecting Supertrees (IOI20_supertrees)	C++20	0 / 100	1 ms	332 KiB

supertrees

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

#define isz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()

using vi = vector<int>;
using vvi = vector<vector<int>>;

struct DSU {
  vi p, sz;
  int n, compo;
  void init(int _n) {
    n = _n;
    compo = n;
    p.resize(n + 1);
    sz.resize(n + 1, 1);
    for (int i = 1; i <= n; i++) p[i] = i;
  }
  int getpar(int x) {
    if (p[x] != x) p[x] = getpar(p[x]);
    return p[x];
  }
  void connect(int x, int y) {
    int a = getpar(x);
    int b = getpar(y);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
  }
  bool same(int x, int y) {
    return getpar(x) == getpar(y);
  }
};

vvi g;

int construct(vvi p) {
	int n = p.size();
  g.resize(n, vector<int>(n, -1));
  for (int i = 0; i < n; i++) {
    int cnt2 = 0, cnt3 = 0;
    for (int j = 0; j < n; j++) {
      if (p[i][j] == 2) cnt2++;
      if (p[i][j] == 3) cnt3++;
    }

    // if (cnt2 == 1 || (cnt3 && cnt3 <= 2)) return 0;

    // if (cnt2 > 0 && cnt3 > 0) return 0;

    vector<int> nodes;
    for (int j = 0; j < n; j++) {
      if ((p[i][j] == 0 && g[i][j] == 1) || (g[i][j] != -1)) return 0;
      if (p[i][j] == 0 || i == j) continue;
      if (p[i][j] == 1) {
        g[i][j] = 1;
        g[j][i] = 1;
        continue;
      }
      nodes.push_back(j);
    }
    if (nodes.empty()) continue;
    for (auto to : nodes) {
      if (g[i][to] != -1) continue;
      g[i][to] = 1;
      g[to][i] = 1;
    }
    for (int j = 1; j < isz(nodes); j++) {
      if (g[nodes[j]][nodes[j - 1]] != -1) continue;
      g[nodes[j]][nodes[j - 1]] = 1;
      g[nodes[j - 1]][nodes[j]] = 1;
    }
    for (int j = 0; j < n; j++) {
      if (p[i][j] < 2) continue;
      if (count(all(nodes), j) == 0) {
        g[nodes.back()][j] = 1;
        g[j][nodes.back()] = 1;
      }
    }
  }
  build(g);
	return 1;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4