제출 #835102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835102		NeroZein	슈퍼트리 잇기 (IOI20_supertrees)	C++17	100 / 100	196 ms	24116 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std; 

int construct(vector<vector<int>> p) {
  int n = p.size();
  int ncc = n; 
  vector<int> pr(n);
  vector<int> sz(n, 1); 
  vector<vector<int>> comp(n);
  iota(pr.begin(), pr.end(), 0);
  for (int i = 0; i < n; ++i) {
    comp[i].push_back(i); 
  }
  function<int(int)> get = [&](int v) {
    return pr[v] = (pr[v] == v ? v : get(pr[v])); 
  };
  function<void(int, int)> unite = [&](int u, int v) {
    u = get(u), v = get(v);
    if (u == v) return;
    if (sz[u] > sz[v]) swap(u, v);
    ncc--;
    pr[u] = v;
    sz[v] += sz[u]; 
    for (int x : comp[u]) {
      comp[v].push_back(x); 
    }
    assert((int) comp[v].size() == sz[v]); 
  };
  for (int i = 0; i < n; ++i) {
    if (p[i][i] != 1) {
      return 0; 
    }
    for (int j = 0; j < n; ++j) {
      if (p[i][j] != p[j][i]) {
        return 0; 
      }
      if (p[i][j] != 0) {
        unite(i, j); 
      }
    }
  }
  int t = 0; 
  vector<int> chosen(n, -1); 
  vector<vector<int>> b(n, vector<int>(n)); 
  auto check = [&](vector<int>& v) {
    for (int i = 0; i < (int) v.size(); ++i) {
      for (int j = 0; j < (int) v.size(); ++j) {
        if (p[v[i]][v[j]] != 1) {
          return false;
        }
      }
      for (int j = 0; j < n; ++j) {
        if (get(j) == get(v[i]) && chosen[j] != chosen[v[i]] && p[j][v[i]] != 2) {
          return false; 
        }
      }
    }
    return true; 
  }; 
  for (int i = 0; i < n; ++i) {
    if (get(i) != i) continue; 
    t++; 
    vector<int> heads;
    vector<int> vec = comp[i];
    for (int j = 0; j < (int) vec.size(); ++j) {
      if (chosen[vec[j]] != -1) continue; 
      int head = vec[j];
      heads.push_back(head); 
      int la = head;
      vector<int> tmp = {head}; 
      chosen[head] = head;
      for (int k = j + 1; k < (int) vec.size(); ++k) {
        if (chosen[vec[k]] == -1 && p[head][vec[k]] == 1) {
          tmp.push_back(vec[k]); 
          chosen[vec[k]] = head;
          b[la][vec[k]] = b[vec[k]][la] = 1; 
          la = vec[k];
        }
      }
      if (!check(tmp)) return 0; 
    }
    if (heads.size() > 1) {
      if (heads.size() == 2) return 0; 
      for (int j = 0; j < (int) heads.size(); ++j) {
        b[heads[j]][heads[(j + 1) % heads.size()]] = 1;
        b[heads[(j + 1) % heads.size()]][heads[j]] = 1;
      }      
    }
    //#warning didn't make sure that an answer exists
  }
  assert(t == ncc); 
  build(b);
  return 1;
}

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