Submission #963860

#	Time	Username	Problem	Language	Result	Execution time	Memory
963860		nguyentunglam	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	174 ms	24228 KiB

supertrees

#include "supertrees.h"
#ifdef ngu
#include "grader.cpp"
#endif // ngu
#include <vector>
#include<bits/stdc++.h>
using namespace std;


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

  auto valid = [&] (vector<int> a, vector<int> b, int c) {
    for(int &j : a) for(int &k : b) if (p[j][k] != c) return false;
    return true;
  };

	vector<int> vis(n), arr;

  auto dfs = [&] (auto self, int u) -> void {
    vis[u] = 1;
    arr.push_back(u);
    for(int v = 0; v < n; v++) if (!vis[v] && p[u][v] == 1) self(self, v);
  };

	std::vector<std::vector<int>> answer(n, vector<int> (n));

  auto add = [&] (int u, int v) {
    answer[u][v] = answer[v][u] = 1;
  };

  vector<vector<int> > connected;

  for(int i = 0; i < n; i++) if (!vis[i]) {
    arr.clear();
    dfs(dfs, i);
    if (!valid(arr, arr, 1)) return 0;
    connected.push_back(arr);
    for(int j = 1; j < arr.size(); j++) {
      answer[arr[j]][arr[j - 1]] = answer[arr[j - 1]][arr[j]] = 1;
    }
  }

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

  for(auto &arr : connected) {
    for(auto &j : arr) for(int k = 0; k < n; k++) if (p[j][k] != p[arr[0]][k]) return 0;
  }

  auto _dfs = [&] (auto self, int u, int c) -> void {
    vis[u] = 1;
    arr.push_back(u);
    for(int v = 0; v < connected.size(); v++) if (!vis[v] && p[connected[u][0]][connected[v][0]] == c) {
      self(self, v, c);
    }
  };

  vector<int> dd(n);

  for(int i = 0; i < connected.size(); i++) if (!vis[i]) {
    arr.clear();
    _dfs(_dfs, i, 2);
    for(int &k : arr) for(int &j : arr) if (j != k) {
      if (p[connected[k][0]][connected[j][0]] != 2) return 0;
    }
    if (arr.size() == 1) continue;
    if (arr.size() < 3) return 0;
    for(int i = 1; i < arr.size(); i++) {
      add(connected[arr[i]][0], connected[arr[i - 1]][0]);
    }
    add(connected[arr[0]][0], connected[arr.back()][0]);
    dd[i] = 1;
  }

  for(int i = 0; i < connected.size(); i++) vis[i] = 0;

  for(int i = 0; i < connected.size(); i++) if (!vis[i]) {
    arr.clear();
    _dfs(_dfs, i, 3);
    for(int &k : arr) for(int &j : arr) if (j != k) {
      if (p[connected[k][0]][connected[j][0]] != 2) return 0;
    }
    if (arr.size() == 1) continue;
    if (arr.size() < 4) return 0;
    for(int i = 1; i < arr.size(); i++) {
      add(connected[arr[i]][0], connected[arr[i - 1]][0]);
    }
    add(connected[arr[0]][0], connected[arr.back()][0]);
    add(connected[arr[1]][0], connected[arr.back()][0]);
    if (dd[i]) return 0;
  }

  build(answer);

	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int j = 1; j < arr.size(); j++) {
      |                    ~~^~~~~~~~~~~~
supertrees.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int i = 0; i < connected.size(); i++) if (!vis[i]) {
      |                  ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 1; i < arr.size(); i++) {
      |                    ~~^~~~~~~~~~~~
supertrees.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for(int i = 0; i < connected.size(); i++) vis[i] = 0;
      |                  ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int i = 0; i < connected.size(); i++) if (!vis[i]) {
      |                  ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i = 1; i < arr.size(); i++) {
      |                    ~~^~~~~~~~~~~~
supertrees.cpp: In instantiation of 'construct(std::vector<std::vector<int> >)::<lambda(auto:24, int, int)> [with auto:24 = construct(std::vector<std::vector<int> >)::<lambda(auto:24, int, int)>]':
supertrees.cpp:62:20:   required from here
supertrees.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int v = 0; v < connected.size(); v++) if (!vis[v] && p[connected[u][0]][connected[v][0]] == c) {
      |                    ~~^~~~~~~~~~~~~~~~~~

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