Submission #401203

#	Time	Username	Problem	Language	Result	Execution time	Memory
401203		my99n	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	283 ms	26800 KiB

supertrees

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

int p[2000], mark[2020];
int find (int u) { return u==p[u]? u:p[u]=find(p[u]); }
bool merge (int i, int j) {
  // cerr << "merge " << find(i) << ' ' << find(j) << endl;
  if (find(i) == find(j)) return false;
  p[find(i)] = find(j);
  return true;
}

void log (vector<vector<int>> s) {
  cerr << "log" << endl;
  for (auto x : s) {
    for (auto y : x) {
      cerr << y << ' ';
    } cerr << endl;
  }
  cerr << endl;
}

vector<int> c;
vector<vector<int>> r;
int n;
void relax(int i) {
  for (int j = i+1; j < n; j++) {
    if (r[i][j] == 2) c.push_back(j);
  }
  c.push_back(i);
  for (auto x : c) {
    for (auto y : c) {
      r[x][y] = r[y][x] = 0;
    }
  }
}

int construct(vector<vector<int>> req) {
  r = req;
  // cerr << "hi" << endl;
	n = req.size();
	vector<vector<int>> answer;
	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}

  iota(p, p+n+1, 0);

  bool flag = true;
  for  (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
      if (req[i][j] == 1) {
        // assert(merge(i, j));
        if (merge(i, j)) {
          answer[i][j] = answer[j][i] = 1;
        }
      }
    }
  }

  for  (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
      if (r[i][j] == 2) {
        c.clear();
        relax(i);
        for (int x = 1; x < c.size(); x++) {
          merge(c[x-1], c[x]);
          answer[c[x-1]][c[x]] = answer[c[x]][c[x-1]] = 1;
        } 
        answer[c.back()][c[0]] = answer[c[0]][c.back()] = 1;
        if (c.size() <= 2) flag = false;
      }
    }
  }

  for  (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
      // cerr << i << ' ' << j << ' ' << find(i) << ' ' << find(j) << endl;
      if (req[i][j] == 0 and find(i) == find(j)) flag = false;
    }
  }

  if (flag == false) return 0;
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int x = 1; x < c.size(); x++) {
      |                         ~~^~~~~~~~~~

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