제출 #963850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
963850		nguyentunglam	슈퍼트리 잇기 (IOI20_supertrees)	C++17	56 / 100	169 ms	22276 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;
  }

  for(int i = 0; i < connected.size(); i++) if (!vis[i]) {
    vis[i] = 1;
    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;
      vis[j] = 1;
      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 &j : g) cout << j << " "; cout << endl;
    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;
}

컴파일 시 표준 에러 (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:50:20: 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 i = 0; i < connected.size(); i++) if (!vis[i]) {
      |                  ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int j = 0; j < connected.size(); j++) if (j != i && p[connected[i][0]][connected[j][0]] == 2) {
      |                    ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i = 1; i < g.size(); i++) {
      |                    ~~^~~~~~~~~~

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