Submission #667198

#	Time	Username	Problem	Language	Result	Execution time	Memory
667198		atigun	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	221 ms	22156 KiB

supertrees

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

using namespace std;
typedef long long ll;

struct dsu{
  vector<int> parent, size;
  int N;
  void assign(int dsusize){
    N = dsusize;
    parent.assign(N, 0);
    iota(parent.begin(), parent.end(), 0);
    size.assign(N, 1);
  }
  int find(int v){
    return parent[v] = (parent[v] == v ? v : find(parent[v]));
  }
  void merge(int v, int u){
    if(find(v) == find(u))
      return;
    if(size[find(v)] < size[find(u)])
      swap(u, v);
    size[find(v)]+= size[find(u)];
    parent[find(u)] = parent[find(v)];
  }
  bool is_same(int v, int u){
    return (find(v) == find(u));
  }
};

dsu DSU;
vector<vector<int>> ans;

void make_edge(int x, int y){
  ans[x][y] = ans[y][x] = 1;
}

int construct(vector<vector<int>> p){
  int n = p.size();
  ans.assign(n, vector<int>(n));
  DSU.assign(n);
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(p[i][j])
        DSU.merge(i, j);
    }
    if(p[i][i] != 1)
      return 0;
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(DSU.is_same(i, j) != (p[i][j] != 0))
        return 0;
    }
  }
  vector<vector<int>> groups(n);
  for(int i = 0; i < n; i++)
    groups[DSU.find(i)].push_back(i);
  for(vector<int>& G : groups){
    if(G.size() <= 1)
      continue;
    vector<int> mid, other;
    mid.reserve(n);
    for(int x : G){
      bool alltwo = true;
      for(int y : G)
        alltwo&= (x == y || p[x][y] == 2);
      if(alltwo)
        mid.push_back(x);
      else
        other.push_back(x);
    }
    vector<int> color(n, -1);
    vector<vector<int>> side(2);
    if(other.size())
      color[other[0]] = 0;
    for(int x : other){
      for(int y : other){
        if(x == y)
          continue;
        if(p[x][y] == 1){
          if(color[y] != -1 && color[y] != color[x])
            return 0;
          color[y] = color[x];
        }
        else if(p[x][y] == 2){
          if(color[y] != -1 && color[y] == color[x])
            return 0;
          color[y] = 1-color[x];
        }
      }
      side[color[x]].push_back(x); 
    }
    if(side[0].size())
      mid.push_back(side[0][0]);
    if(side[1].size())
      mid.push_back(side[1][0]);
    if(mid.size() == 2)
      return 0;
    if(mid.size() > 1)
      for(int i = 0; i < (int) (mid.size()); i++)
        make_edge(mid[i], mid[(i+1)%((int) (mid.size()))]);
    for(int i = 1; i < (int) (side[0].size()); i++)
      make_edge(side[0][i], side[0][i-1]);
    for(int i = 1; i < (int) (side[1].size()); i++)
      make_edge(side[1][i], side[1][i-1]);
  }
  build(ans);
  return 1;
}

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