Submission #835095

#	Time	Username	Problem	Language	Result	Execution time	Memory
835095		NeroZein	Connecting Supertrees (IOI20_supertrees)	C++17	46 / 100	171 ms	24064 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<bool> chosen(n); 
  vector<vector<int>> b(n, vector<int>(n)); 
  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]]) continue; 
      int head = vec[j];
      heads.push_back(head); 
      int la = head;
      chosen[head] = true;
      for (int k = j + 1; k < (int) vec.size(); ++k) {
        if (!chosen[vec[k]] && p[head][vec[k]] == 1) {
          chosen[vec[k]] = true;
          b[la][vec[k]] = b[vec[k]][la] = 1; 
          la = vec[k];
        }
      }
    }
    if (heads.size() > 1) {
      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;
}

Compilation message (stderr)

supertrees.cpp:72:18: warning: missing terminating ' character
   72 |     #warning didn't make sure that an answer exists
      |                  ^
supertrees.cpp:72:6: warning: #warning didn't make sure that an answer exists [-Wcpp]
   72 |     #warning didn't make sure that an answer exists
      |      ^~~~~~~

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