제출 #361417

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361417		Hegdahl	슈퍼트리 잇기 (IOI20_supertrees)	C++17	65 / 100	297 ms	22508 KiB

supertrees

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

using namespace std;

const int mxN = 1000;

vector<int> boss1(mxN), boss2(mxN), under1(mxN, 1), under2(mxN, 1);

int find1(int i) {
  if (boss1[i] == i) return i;
  return boss1[i] = find1(boss1[i]);
}
int find2(int i) {
  if (boss2[i] == i) return i;
  return boss2[i] = find2(boss2[i]);
}

void unite1(int i, int j) {
  i = find1(i);
  j = find1(j);
  if (i == j) return;
  if (under1[i] > under1[j]) swap(i, j);
  under1[j] += under1[i];
  boss1[i] = j;
}
void unite2(int i, int j) {
  i = find2(i);
  j = find2(j);
  if (i == j) return;
  if (under2[i] > under2[j]) swap(i, j);
  under2[j] += under2[i];
  boss2[i] = j;
}



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

  for (int i = 0; i < n; ++i) boss1[i] = boss2[i] = i;

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i == j && p[i][j]!=1) return 0;
      if (p[i][j] == 1) unite1(i, j);
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (p[i][j] == 2) unite2(find1(i), find1(j));
    }
  }

  for (int _i = 0; _i < n; ++_i) {
    for (int _j = 0; _j < n; ++_j) {
      if (_i == _j) continue;
      int i = find1(_i), j = find1(_j);
      if (p[i][j] == 3) { cerr << "3!\n"; return 0; };
      if ((p[i][j]==0 || p[i][j]==2) && i==j) { cerr << "same tree\n"; return 0; }
      if (p[i][j]==0 && find2(i) == find2(j)) { cerr << "same cycle\n"; return 0; }
    }
  }

  vector<vector<int>> ans(n, vector<int>(n));

  for (int i = 0; i < n; ++i) {
    if (find1(i) != i) ans[i][boss1[i]] = ans[boss1[i]][i] = 1;
  }

  vector<int> cycles[n];

  for (int i = 0; i < n; ++i) {
    if (boss1[i] == i) {
      cycles[find2(i)].push_back(i);
    }
  }

  for (int i = 0; i < n; ++i) {
    if (cycles[i].size() == 2) return 0;

    if (cycles[i].size() <= 1) continue;

    for (int j = 0; j < (int)cycles[i].size(); ++j) {
      ans[cycles[i][(j+1)%cycles[i].size()]][cycles[i][j]] =
      ans[cycles[i][j]][cycles[i][(j+1)%cycles[i].size()]] = 1;
    }
  }

  build(ans);

  return 1;
}

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