제출 #362531

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
362531		valerikk	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	280 ms	28348 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

struct dsu {
  vector<int> p;
   
  int get(int v) {
    return p[v] == v ? v : p[v] = get(p[v]);
  }

  bool uni(int v, int u) {
    v = get(v), u = get(u);
    p[v] = u;
    return v != u;
  }

  dsu() {}
  dsu(int n) {
    p = vector<int>(n);         
    for (int i = 0; i < n; i++) p[i] = i;
  }
};

int construct(vector<vector<int>> p) {
  int n = p.size();
  vector<vector<int>> g(n);
  for (int i = 0; i < n; i++) {
    if (p[i][i] != 1) return 0;
    for (int j = 0; j < i; j++) {
      if (p[i][j] != p[j][i]) return 0;
      if (p[i][j] == 3) return 0;
      g[i].push_back(j);
      g[j].push_back(i);
    }
  }    
  vector<bool> vis(n, false);
  vector<int> ind(n, -1);
  vector<int> comp;
  function<void(int, int)> dfs = [&](int v, int f) {
    comp.push_back(v);
    vis[v] = true;
    ind[v] = f;
    for (int u : g[v]) {
      if (!vis[u]) {
        dfs(u, f);
      }
    }
  };
  vector<pair<int, int>> ed;                
  for (int st = 0; st < n; st++) {
    if (!vis[st]) {
      comp = {};
      dfs(st, st);
      bool ok = true;
      bool cycle = false;            
      for (int v : comp) {
        for (int u : comp) {
          ok &= p[v][u] != 0; 
          cycle |= p[v][u] == 2;
        }
      }
      for (int v : comp) {
        for (int i = 0; i < n; i++) {
          if (ind[i] != st) ok &= p[v][i] == 0;
        }
      }     
      if (!ok) return 0; 
      int sz = comp.size();
      dsu d(n);             
      for (int v : comp) {
        for (int u : comp) {
          if (p[v][u] == 1) d.uni(v, u);
        }
      }   
      for (int v : comp) {
        for (int u : comp) {
          int kek = 1 + (d.get(v) != d.get(u));
          ok &= kek == p[v][u];  
        }
      }
      if (!ok) return 0;
      if (cycle) {
        vector<int> arr;
        for (int v : comp) arr.push_back(d.get(v));
        sort(arr.begin(), arr.end());
        arr.erase(unique(arr.begin(), arr.end()), arr.end());
        if (arr.size() < 3) return 0;
        for (int i = 0; i < arr.size(); i++) ed.push_back({arr[i], arr[(i + 1) % arr.size()]});
        vector<vector<int>> have(arr.size());
        for (int v : comp) {
          have[lower_bound(arr.begin(), arr.end(), d.get(v)) - arr.begin()].push_back(v);
        }                 
        for (int i = 0; i < arr.size(); i++) {
          for (int j = 0; j + 1 < have[i].size(); j++) {
            ed.push_back({have[i][j], have[i][j + 1]});
          }
        }

      } else {
        for (int i = 0; i + 1 < comp.size(); i++) ed.push_back({comp[i], comp[i + 1]});
      }
    }
  }                       
  vector<vector<int>> ret(n, vector<int>(n, 0));
  for (auto e : ed) {
    ret[e.first][e.second] = 1;
    ret[e.second][e.first] = 1;
  }
  build(ret);
  return 1;
}

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for (int i = 0; i < arr.size(); i++) ed.push_back({arr[i], arr[(i + 1) % arr.size()]});
      |                         ~~^~~~~~~~~~~~
supertrees.cpp:95:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for (int i = 0; i < arr.size(); i++) {
      |                         ~~^~~~~~~~~~~~
supertrees.cpp:96:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |           for (int j = 0; j + 1 < have[i].size(); j++) {
      |                           ~~~~~~^~~~~~~~~~~~~~~~
supertrees.cpp:102:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (int i = 0; i + 1 < comp.size(); i++) ed.push_back({comp[i], comp[i + 1]});
      |                         ~~~~~~^~~~~~~~~~~~~
supertrees.cpp:70:11: warning: unused variable 'sz' [-Wunused-variable]
   70 |       int sz = comp.size();
      |           ^~

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