Submission #667104

#	Time	Username	Problem	Language	Result	Execution time	Memory
667104		atigun	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	193 ms	22148 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);
  bool ok = 1;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      ok&= (p[i][j] == p[j][i]);
      if(p[i][j])
        DSU.merge(i, j);
    }
    ok&= (p[i][i] == 1);
  }
  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      ok&= (DSU.is_same(i, j) == (p[i][j] != 0));
  if(!ok)
    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((int) (G.size()) <= 1)
      continue;
    vector<int> all_two, is_two(n, 1);
    all_two.reserve(n);
    for(int I : G){
      for(int J : G)
        is_two[I]&= (I == J || p[I][J] == 2);
      if(is_two[I])
        all_two.push_back(I);
    }
    for(int i = 1; i < (int) (all_two.size()); i++)
      make_edge(all_two[i-1], all_two[i]);
    vector<int> color(n, -1);
    color[G[0]] = 0;
    for(int i = 0; i < (int) (G.size()); i++){
      if(is_two[G[i]])
        continue;
      for(int j = i+1; j < (int) (G.size()); j++){
        if(is_two[G[j]])
          continue;
        if(p[G[i]][G[j]] == 1){
          ok&= (color[G[j]] == -1 || color[G[j]] == color[G[i]]);
          color[G[j]] = color[G[i]];
        } else if(p[G[i]][G[j]] == 2){
          ok&= (color[G[j]] == -1 || color[G[j]] == (color[G[i]]^1));
          color[G[j]] = color[G[i]]^1;
        }
      }
    }
    if(!ok)
      break;
    vector<vector<int>> side(2);
    for(int I : G){
      if(is_two[I] || color[I] == -1)
        continue;
      side[color[I]].push_back(I);
    }
    for(int i = 1; i < (int) (side[0].size()); i++)
      make_edge(side[0][i-1], side[0][i]);
    for(int i = 1; i < (int) (side[1].size()); i++)
      make_edge(side[1][i-1], side[1][i]);
    if(all_two.size()){
      if(side[0].size() && (int) (side[1].size())){
        make_edge(side[0].back(), side[1][0]);
        make_edge(side[0].back(), all_two[0]);
        make_edge(side[1][0], all_two.back());
      } else if((int) (side[0].size()) && side[1].empty()){
        ok&= ((int) (all_two.size()) >= 2);
        ok&= ((int) (side[0].size()) > 1);
        make_edge(side[0].back(), all_two[0]);
        make_edge(side[0].back(), all_two.back());
      } else if(side[0].empty() && (int) (side[1].size())){
        ok&= ((int) (all_two.size()) >= 2);
        ok&= ((int) (side[1].size()) > 1);
        make_edge(side[0][0], all_two.back());
        make_edge(side[0][0], all_two[0]);
      } else if(side[0].empty() && side[1].empty()){
        ok&= ((int) (all_two.size()) >= 2);
        make_edge(all_two[0], all_two.back());
      }
    } else{
      ok&= (side[1].empty());
    }
  }
  if(!ok)
    return 0;
  build(ans);
  return 1;
}

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