Submission #401208

#	Time	Username	Problem	Language	Result	Execution time	Memory
401208		my99n	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	284 ms	26052 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] != 0) 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);
        int first = -1, last = 0;
        for (int x = 1; x < c.size(); x++) {
          if (merge(c[last], c[x])) {
            answer[c[last]][c[x]] = answer[c[x]][c[last]] = 1;
            if (first == -1) first = x-1;
            last = x;
          }
        } 
        if (first == -1 or c.size() <= 2) {
          flag = false;
          continue;
        }
        answer[c[last]][c[first]] = answer[c[first]][c[last]] = 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;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:70:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         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