Submission #1197766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197766		vyaduct	Connecting Supertrees (IOI20_supertrees)	C++20	40 / 100	125 ms	22252 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;

#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define vt vector
#define pb push_back

class DSU {
public:
  vt<int>p, size;
  void init(int n){
    p.resize(n);
    size.resize(n);
    for (int i=0;i<n;i++){
      p[i] = i;
      size[i] = 1;
    }
  }

  int get(int a){
    return p[a] = (p[a] == a ? a : get(p[a]));
  }

  void unite(int a, int b){
    a = get(a);
    b = get(b);
    if (a == b) return;
    if (size[a] > size[b]) swap(a,b);
    size[b] += size[a];
    p[a] = b;
  }
};

int construct(vt<vt<int>> p){
  int n = sz(p);
  vt<vt<int>> b(n, vt<int>(n));
  for (int i=0;i<n;i++){
    for (int j=0;j<n;j++){
      b[i][j] = 0;
    }
  }
  DSU cc, one, two;
  cc.init(n);
  one.init(n);
  two.init(n);
  for (int i=0;i<n;i++){
    for (int j=0;j<n;j++){
      if (p[i][j] != 0) cc.unite(i,j);
      if (p[i][j] == 1) one.unite(i,j);
      if (p[i][j] == 2) two.unite(i,j);
    }
  }
  for (int i=0;i<n;i++){
    for (int j=0;j<n;j++){
      if (p[i][j] == 0 && cc.get(i) == cc.get(j)) return 0;
    }
  }
  map<int,vt<int>> ones;
  for (int i=0;i<n;i++){
    ones[one.get(i)].pb(i);
  }
  vt<bool> processed(n, false);
  for (auto &[x,v]: ones){
    if (v.size() == 1 && processed[v[0]]) continue;
    sort(all(v)); v.erase(unique(all(v)), v.end());
    for (int i=0;i<v.size()-1;i++){
      b[v[i]][v[i+1]] = 1;
      b[v[i+1]][v[i]] = 1;
      processed[v[i]]=1;
      processed[v[i+1]]=1;
    }
    //cout << "v = : ";
    //for (auto x: v){
    //  cout << x << " ";
    //} cout << endl;
    int tail = v.back();
    //cout << "tail = " << tail << endl;
    vt<int> twos;
    for (auto x: v){
      for (int y=0;y<n;y++){
        if (p[x][y] == 2) twos.pb(y);
      }
    }
    sort(all(twos)); twos.erase(unique(all(twos)), twos.end());
    // cout << "twos = : ";
    //for (auto x: twos){
    //  cout << x << " ";
    //} cout << endl;
    if (twos.size()+1==2) return false;
    if (twos.size()>0){
      b[tail][twos[0]]=1;
      b[twos[0]][tail]=1;
      for (int i=0;i<twos.size()-1;i++){
        b[twos[i]][twos[i+1]] = 1;
        b[twos[i+1]][twos[i]] = 1;
        processed[twos[i]]=1;
        processed[twos[i+1]]=1;
      }
      b[tail][twos.back()]=1;
      b[twos.back()][tail]=1;
    }
  }
  build(b);
  return 1;
}

/*
7
2 2 2 0 0 0 0 
2 2 2 0 0 0 0 
2 2 2 0 0 0 0
0 0 0 2 0 2 2
0 0 0 0 2 0 0
0 0 0 2 0 2 2
0 0 0 2 0 2 2
*/

/*
9
1 1 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0
0 0 1 1 2 2 0 0 0
0 0 1 1 2 2 0 0 0
0 0 2 2 1 2 0 0 0
0 0 2 2 2 1 0 0 0
0 0 0 0 0 0 1 2 2
0 0 0 0 0 0 2 1 2
0 0 0 0 0 0 2 2 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