Submission #1278424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278424		SonicML	슈퍼트리 잇기 (IOI20_supertrees)	C++17	100 / 100	114 ms	26156 KiB

supertrees

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

using namespace std;

int n;

int const NMAX = 1000;
int comp[3][NMAX]; 
int path[NMAX][NMAX];
int last[1 + NMAX];
int cleng[1 + NMAX];

void buildComp(int special, int node, int rep) {
  //cerr << special << ' ' << node << ' ' << rep << '\n';
  if(comp[special][node] == -1) {
    comp[special][node] = rep;
    for(int i = 0;i < n;i++) {
      if(path[node][i] != 0 && path[node][i] <= special) {
        buildComp(special, i, rep);
      } 
    }
  } 
}

bool computeIsGood() {
  for(int i = 0;i < n;i++) {
    for(int j = i+1;j < n;j++) {
      if(comp[1][i] == comp[1][j] && path[i][j] != 1) {
	//cerr << "r1 " << i << ' ' << j << ' ' << path[i][j] << '\n';
	return false;
      } else if(comp[2][i] == comp[2][j] && path[i][j] == 0) {
	//cerr << "r2 " << i << ' ' << j << ' ' << path[i][j] << '\n';
        return false;
      }
    }
  }
  return true;
}

int construct(vector<vector<int>> p) {
  n = p.size();
  vector<vector<int>> sol;
  for (int i = 0; i < n; i++) {
    vector<int> row;
    row.resize(n);
    sol.push_back(row);
  }
  //cerr << "done creation of sol\n";
  for(int i = 0;i < n;i++) {
    comp[1][i] = comp[2][i] = -1;
    last[i] = -1;
  }
  for(int i = 0;i < n;i++) { 
    if(p[i][i] != 1) {
      return 0;
    }
    for(int j = 0;j < n;j++) {
      path[i][j] = p[i][j];
      if(p[i][j] == 3 || p[i][j] != p[j][i]) {
        return 0;
      } 
    }
  }
  //cerr << "done creation of path\n";
  //cerr << "first buildComp\n  ";
  for(int i = 0;i < n;i++) {
    buildComp(1, i, i);
    //cerr << comp[1][i] << ' ';
  } 
  //cerr << '\n';
  //cerr << "second buildComp\n  ";
  for(int i = 0;i < n;i++) { 
    buildComp(2, i, i);
    //cerr << comp[2][i] << ' ';
  }
  //cerr << '\n';
  bool isGood = computeIsGood();
  if(!isGood) {
    return 0;
  }
  // build chains
  for(int i = 0;i < n;i++) { 
    if(last[comp[1][i]] != -1) {
      int temp = last[comp[1][i]]; 
      sol[i][temp] = sol[temp][i] = 1; 
    }
    last[comp[1][i]] = i; 
  }
  //cerr << "built chains\n";
  // reset last
  for(int i = 0;i < n;i++) {
    last[i] = -1;
  }
  // build cycles
  for(int i = 0;i < n;i++) {
    if(comp[1][i] == i) {
      if(last[comp[2][i]] != -1) {
        int temp = last[comp[2][i]];
	sol[i][temp] = sol[temp][i] = 1;
	cleng[comp[2][i]]++;
      } 
      last[comp[2][i]] = i;
    }
  }
  for(int i = 0;i < n;i++) {
    if(comp[1][i] == i) {
      if(comp[2][i] == i && last[i] != i) {
        sol[i][last[i]] = sol[last[i]][i] = 1;
	cleng[comp[2][i]]++;
      }
    }
  }
  for(int i = 0;i < n;i++) {
    if(comp[1][i] == i && comp[2][i] == i) {
      if(cleng[comp[2][i]] == 2 || cleng[comp[2][i]] == 1) {
	return false;
      }
    }
  }
  //cerr << "built cycles\n";
  build(sol);
  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