Submission #437658

#	Time	Username	Problem	Language	Result	Execution time	Memory
437658		xiaowuc1	Connecting Supertrees (IOI20_supertrees)	C++17	Compilation error	0 ms	0 KiB

supertrees

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
// END NO SAD

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<ll>> matrix;

int find(vector<int>& p, int x) {
  return p[x] == x ? x : (p[x] = find(p, p[x]));
}
void merge(vector<int>& p, int x, int y) {
  p[find(p, x)] = find(p, y);
}

int construct(vector<vector<int>> p) {
  int n = sz(p);
  vector<vector<int>> ret;
  for(int i = 0; i < n; i++) {
    vector<int> t(n);
    ret.pb(t);
  }
  for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j] == 3) return 0;
  vector<int> connectedcomponent(n);
  iota(all(connectedcomponent), 0);
  for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j]) merge(connectedcomponent, i, j);
  // check zero
  for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j] == 0 && find(connectedcomponent, i) == find(connectedcomponent, j)) return 0;
  // check one
  vector<int> oneedge(n);
  iota(all(oneedge), 0);
  for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j] == 1) merge(oneedge, i, j);
  for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j] != 1 && find(oneedge, i) != find(oneedge, j)) return 0; 
  map<int, int> treetoroot;
  for(int i = 0; i < n; i++) {
    if(!treetoroot.count(find(oneedge, i))) {
      treetoroot[find(oneedge, i)] = i;
    }
    else {
      ret[find(oneedge, i)][i] = 1;
      ret[i][find(oneedge, i)] = 1;
    }
  }
  map<int, set<int>> roots;
  for(int i = 0; i < n; i++) {
    roots[find(connectedcomponent, i)].insert(treetoroot[find(oneedge, i)]);
  }
  for(auto out: roots) {
    if(sz(out.s) == 2) return 0;
    if(sz(out.s) == 1) continue;
    vector<int> v(all(out.s));
    for(int i = 0; i < sz(v); i++) {
      int j = (i+1)%sz(v);
      ret[v[i]][v[j]] = 1;
      ret[v[j]][v[i]] = 1;
    }
  }
  build(ret);
  return 1;
}

void solve() {
}

// what would chika do
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
// are you doing geometry in floating points

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:87:3: error: 'build' was not declared in this scope
   87 |   build(ret);
      |   ^~~~~