Submission #713395

#	Time	Username	Problem	Language	Result	Execution time	Memory
713395		garyye	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	212 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
template<class T> bool cmin(T& a, T b) { if(a > b) { a = b; return true; } return false; }
template<class T> bool cmax(T& a, T b) { if(a < b) { a = b; return true; } return false; }
typedef pair<int, int> pii;
#define SZ(x) ((int) (x.size()))
#define fi first
#define se second

const int N = 2222;
int n;
int vis[N];
int root[N];

vector<vector<int>> p, b;
vector<int> roots, t;

void add(int u, int v) {
  b[u][v] = b[v][u] = 1;
}

void dfs(int u) {
  t.push_back(u);
  vis[u] = 1;
  for(int v = 0; v < n; ++v) {
    if(u == v || vis[v] || p[u][v] != 1) 
      continue;
    dfs(v);
  }
}

void rec(int u) {
  vis[u] = true;
  t.push_back(u);
  for(int v: roots) {
    if(p[u][v] == 2 && !vis[v]) {
      rec(v);
    }
  }
}

int construct(vector<vector<int>> _p) { 
  p = _p;
  n = p.size();
  b = vector<vector<int>>(n, vector<int>(n, 0));

  // Last subtask
  for(auto& a: p) 
    for(auto& b: a) 
      if(b == 3) 
        return 0;

  for(int foo = 0; foo < n; foo++) {
    if(vis[foo])
      continue;
    t.clear();
    dfs(foo);
    for(int i: t) {
      for(int j = 0; j < n; ++j) {
        if(p[i][j] != p[t[0]][j]) {
          return 0;
        }
      }
    }
    // Can name anyone the root since they all the same
    for(int i = 0; i + 1 < SZ(t); ++i) {
      add(t[i], t[i + 1]);
      root[t[i + 1]] = t[0];
    }
    roots.push_back(t[0]);
  }

  printf("Roots=%d\n", SZ(roots));

  memset(vis, 0, sizeof vis);
  for(int u: roots) {
    if(vis[u])
      continue;
    t.clear();
    rec(u);

    if(SZ(t) == 2)
      return 0;
    if(SZ(t) == 1)
      continue;
    for(int x: t) 
      for(int y: t) 
        if(x != y && p[x][y] != 2)
          return 0;
    for(int i = 0; i < SZ(t); ++i) {
      add(t[i], t[(i+1)%SZ(t)]);
    }
  }

  build(b);
  return 1;
}

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