Submission #963848

#	Time	Username	Problem	Language	Result	Execution time	Memory
963848		nguyentunglam	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	162 ms	22192 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(int i = 0; i < connected.size(); i++) if (!vis[i]) {
    vector<int> zip, g;
    g.push_back(i);
    for(auto &k : connected[i]) zip.push_back(k);
    for(int j = 0; j < connected.size(); j++) if (j != i && p[connected[i][0]][connected[j][0]] == 2) {
      if (vis[j]) return 0;
      if (!valid(zip, connected[j], 2)) return 0;
      for(auto &k : connected[j]) zip.push_back(k);
      g.push_back(j);
    }
    if (g.size() == 1) continue;
    if (g.size() < 3) return 0;
    for(int i = 1; i < g.size(); i++) {
      add(connected[g[i]][0], connected[g[i - 1]][0]);
    }
    add(connected[g[0]][0], connected[g.back()][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:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(int i = 0; i < connected.size(); i++) if (!vis[i]) {
      |                  ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int j = 0; j < connected.size(); j++) if (j != i && p[connected[i][0]][connected[j][0]] == 2) {
      |                    ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i = 1; i < g.size(); i++) {
      |                    ~~^~~~~~~~~~

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