Submission #667194

#	Time	Username	Problem	Language	Result	Execution time	Memory
667194		atigun	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	214 ms	22168 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++){
      if(p[i][j] != p[j][i])
        return 0;
      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(mid.empty() && !side[1].empty())
      return 0;
    if(side[0].size()){
      mid.insert(mid.begin(), side[0].back());
      side[0].pop_back();
    }
    if(side[1].size()){
      mid.push_back(side[0][0]);
      side[1].erase(side[1].begin());
    }
    if(mid.size() > 1){
      if(mid.size() == 2)
        return 0;
      for(int i = 0; i < mid.size(); i++){
        make_edge(mid[i], mid[(i+1)%((int) (mid.size()))]);
      }
    }
    for(int i = 0; i+1 < (int) (side[0].size()); i++)
      make_edge(side[0][i], side[0][i+1]);
    for(int i = 0; i+1 < (int) (side[1].size()); i++)
      make_edge(side[1][i], side[1][i+1]);
    if(mid.size()){
      if(side[0].size()){
        make_edge(side[0].back(), mid[0]);
      }
      if(side[1].size()){
        make_edge(side[1][0], mid.back());
      }
    }
  }
  build(ans);
  return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:111:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |       for(int i = 0; i < mid.size(); i++){
      |                      ~~^~~~~~~~~~~~
supertrees.cpp:43:8: warning: unused variable 'ok' [-Wunused-variable]
   43 |   bool ok = 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