Submission #388396

#	Time	Username	Problem	Language	Result	Execution time	Memory
388396		WLZ	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	300 ms	24212 KiB

supertrees

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

vector< vector<int> > ans;
vector<int> p;

int root(int x) {
  if (p[x] == -1) return x;
  return p[x] = root(p[x]);
}

void connect(int x, int y, bool b = true) {
  x = root(x); y = root(y);
  if (x != y) {
    p[y] = x;
    if (b) ans[x][y] = ans[y][x] = 1;
  }
}

int construct(vector< vector<int> > a) {
	int n = a.size();
  ans.assign(n, vector<int>(n, 0));
  p.assign(n, -1);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (a[i][j] >= 3) return 0;
      if (a[i][j] == 1) connect(i, j);
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (root(i) == root(j) && a[i][j] != 1) return 0;
    }
  }
  vector<bool> is_root(n);
  for (int i = 0; i < n; i++) is_root[i] = root(i) == i;
  p.assign(n, -1);
  for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (is_root[i] && is_root[j] && a[i][j] == 2) connect(i, j, false);
  for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i != j && root(i) == root(j) && a[i][j] != 2) return 0; 
  for (int i = 0; i < n; i++) {
    if (root(i) != i) continue;
    vector<int> tmp;
    for (int j = 0; j < n; j++) if (root(j) == i) tmp.push_back(j);
    if ((int) tmp.size() == 1) continue;
    if ((int) tmp.size() == 2) return 0;
    for (int i = 1; i < (int) tmp.size(); i++) ans[tmp[i - 1]][tmp[i]] = ans[tmp[i]][tmp[i - 1]] = 1;
    ans[tmp[0]][tmp.back()] = ans[tmp.back()][tmp[0]] = 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