Submission #667216

#	Time	Username	Problem	Language	Result	Execution time	Memory
667216		atigun	슈퍼트리 잇기 (IOI20_supertrees)	C++17	100 / 100	214 ms	24032 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])
        DSU.merge(i, j);
      if(p[i][j] == 3)
        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<bool> vis(n);
    for(int x : other){
      if(vis[x])
        continue;
      vector<int> side = {x};
      mid.push_back(x);
      vis[x] = true;
      for(int y : other){
        if(p[x][y] == 1 && x != y){
          if(vis[y])
            return 0;
          side.push_back(y);
          vis[y] = 1;
        }
      }
      for(int k1 : side){
        for(int k2 : side){
          if(p[k1][k2] != 1)
            return 0;
        }
      }
      for(int i = 1; i < side.size(); i++)
        make_edge(side[i], side[i-1]);
    }
    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()))]);
  }
  build(ans); 
  return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:96:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |       for(int i = 1; i < side.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: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4