Submission #523870

#	Time	Username	Problem	Language	Result	Execution time	Memory
523870		Turkhuu	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	203 ms	28108 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

struct dsu{
  int n;
  vector<int> size, parent;
 
  dsu(int _n) : n(_n), size(n, 1), parent(n){
    iota(parent.begin(), parent.end(), 0);
  }
 
  int get(int a){
    return a == parent[a] ? a : parent[a] = get(parent[a]);
  }
 
  bool unite(int a, int b){
    a = get(a);
    b = get(b);
    if(a == b){
      return 0;
    }
    if(size[a] > size[b]){
      swap(a, b);
    }
    size[b] += size[a];
    parent[a] = b;
    return 1;
  }
};


int construct(vector<vector<int>> a){
	int n = a.size();
  vector<vector<int>> ans(n, vector<int>(n, 0));
	dsu s(n);
	vector<vector<int>> v(n);
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			if(a[i][j] == 1){
				v[i].push_back(j);
				v[j].push_back(i);
			} else if(a[i][j] == 2){
				s.unite(i, j);
			} else if(a[i][j] == 3){
        return 0;
      }
		}
	}
	vector<bool> b(n, false);
	for(int i = 0; i < n; i++){
		if(i != s.parent[i]){
			continue;
		}
    if(s.size[i] == 2){
      return 0;
    }
    if(s.size[i] == 1){
      continue;
    }
		b[i] = true;
		int cur = i, last = i;
		for(int j = 0; j < n; j++){
			if(!b[j] && s.get(j) == i){
				last = j;
				ans[cur][j] = 1;
				ans[j][cur] = 1;
				for(int k : v[j]){
					if(s.get(k) != i){
            return 0;
					}
					ans[j][k] = 1;
					ans[k][j] = 1;
          b[k] = true;
				}
        b[j] = true;
        cur = j;
			}
		}
    ans[i][last] = 1;
    ans[last][i] = 1;
	}
  for(int i = 0; i < n; i++){
    if(!b[i]){
      for(int j : v[i]){
        if(b[j]){
          return 0;
        }
        b[j] = true;
        ans[i][j] = 1;
        ans[j][i] = 1;
      }
    }
  }
	build(ans);
	return 1;
}

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