Submission #310195

#	Time	Username	Problem	Language	Result	Execution time	Memory
310195		Lemur95	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	258 ms	22272 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
#pragma GCC optimize("Ofast")
#define x first
#define y second
#define ld long double
#define ll long long

using namespace std;

/*void build(vector <vector <int>> b) {
  for(int i = 0; i < b.size(); i++) {
    for(int j = 0; j < b[i].size(); j++)
      cout << b[i][j] << " ";
    cout << "\n";
  }
}*/

int construct(vector <vector <int>> p) {
  int n = p.size();
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      if(p[i][j] == 3)
        return 0;
    }
  }
  // structures can be like: a chain and a cycle / a cycle / a chain
  // nodes in cycle have all values in p = 2 or 0
  vector <vector <int>> adj(n);
  vector <int> comp(n), chain(n), from(n, -1), nodes;
  vector <bool> viz(n);
  int cnt = 0;
  for(int i = 0; i < n; i++)
    adj[i].resize(n);
  for(int i = 0; i < n; i++) {
    if(!comp[i])
      comp[i] = ++cnt;
    else
      continue;
    for(int j = 0; j < n; j++) {
      if(p[i][j])
        comp[j] = cnt;
    }
  }
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      if((comp[i] == comp[j]) ^ (p[i][j] != 0))
        return 0;
    }
  }
  cnt = 0;
  for(int i = 0; i < n; i++) {
    if(!chain[i])
      chain[i] = ++cnt, nodes.push_back(i);
    else
      continue;
    for(int j = 0; j < n; j++) {
      if(p[i][j] == 1) {
        chain[j] = cnt;
        from[j] = i;
      }
    }
  }
  for(int i = 0; i < n; i++) {
    if(from[i] >= 0 && from[i] != i)
      adj[i][from[i]] = adj[from[i]][i] = 1;
  }
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      if((chain[i] == chain[j] ^ (p[i][j] == 1)))
        return 0;
    }
  }
  for(auto &i : nodes) {
    if(viz[i])
      continue;
    vector <int> v;
    for(auto &j : nodes) {
      if(!viz[j] && comp[i] == comp[j])
        v.push_back(j), viz[j] = 1;
    }
    if(v.size() == 2)
      return 0;
    if(v.size() == 1)
      continue;
    for(int j = 0; j < v.size(); j++) {
      int k = (j + 1) % v.size();
      if(v[k] != v[j])
        adj[v[j]][v[k]] = adj[v[k]][v[j]] = 1;
    }
  }
  build(adj);
  return 1;
}

/*int main() {
  int n;
  vector <vector <int>> p;
  cin >> n;
  p.resize(n);
  for(int i = 0; i < n; i++) {
    p[i].resize(n);
    for(int j = 0; j < n; j++)
      cin >> p[i][j];
  }
  cout << construct(p);
  return 0;
}*/

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:70:20: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   70 |       if((chain[i] == chain[j] ^ (p[i][j] == 1)))
supertrees.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int j = 0; j < v.size(); j++) {
      |                    ~~^~~~~~~~~~

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