Submission #771025

#	Time	Username	Problem	Language	Result	Execution time	Memory
771025		cadmiumsky	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	175 ms	27760 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

vector<vector<int>> rez;

void addedge(int a, int b) {
  rez[a][b] = rez[b][a] = 1;
  return;
}

int construct(std::vector<std::vector<int>> p) {
  int n;
  for(auto v : p)
    for(auto x : v) {
      if(x == 3) return 0;
    } 
  n = sz(p);
  for(int i = 0; i < n; i++)
    if(p[i][i] != 1) return 0;
  rez.resize(n, vector<int>(n, 0));
  //cerr << n << '\n';
  map<vector<int>, vector<int>> group;
  vector<int> eligible(n, 0);
  for(int i = 0; i < n; i++) 
    group[p[i]].emplace_back(i);
  
  for(auto &[a, b] : group) {
    //cerr << sz(b) << '\n';
    for(int i = 1; i < sz(b); i++)
      addedge(b[0], b[i]);
    eligible[b[0]] = 1;
  }
  //cerr << "ok\n";
  group.clear();
    
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      p[i][j] *= eligible[i] * eligible[j];
      if(i == j) p[i][j] *= 2;
      if(p[i][j] == 1) return 0;
    }
    if(eligible[i])
      group[p[i]].emplace_back(i);
  }
  
  vector<int> coloring(n);
  int C = 0;
  
  for(auto &[a, b] : group) {
    C++;
    for(auto x : b)
      coloring[x] = C;
    if(sz(b) == 1) continue;
    if(sz(b) == 2) return 0;
    for(int i = 0, j = 1; i < sz(b); i++, j = (j + 1) % sz(b)) {
      addedge(b[i], b[j]);
    }
  }
  
  for(int i = 0; i < n; i++) {
    if(!eligible[i]) continue;
    for(int j = 0; j < n; j++) {
      if(!eligible[j]) continue;
      if(p[i][j] == 2) {
        if(!(coloring[i] == coloring[j]))
          return 0;
      }
        
    }
  }
  
  build(rez);
  return 1;
  

}



/**
      Anul asta se da centroid.
-- Surse oficiale
*/

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