Submission #401197

#	Time	Username	Problem	Language	Result	Execution time	Memory
401197		my99n	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	262 ms	22596 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;
}

int construct(vector<vector<int>> req) {
  // cerr << "hi" << endl;
	int 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++) {
      // 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;
}

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