Submission #1200829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200829		Kerim	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	328 KiB

supertrees

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
using ll = long long;

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const char nl = '\n';
//const int N = 1e5+10;

class DisjointSets {
  private:
    vector<int> parents;
    vector<int> sizes;

  public:
    DisjointSets(int size) : parents(size), sizes(size, 1) {
        for (int i = 0; i < size; i++) { parents[i] = i; }
    }

    /** @return the "representative" node in x's component */
    int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }

    /** @return whether the merge changed connectivity */
    bool unite(int x, int y) {
        int x_root = find(x);
        int y_root = find(y);
        if (x_root == y_root) { return false; }

        parents[y_root] = x_root;
        return true;
    }

    /** @return whether x and y are in the same connected component */
    bool connected(int x, int y) { return find(x) == find(y); }
};

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	DisjointSets tree(n);
	vector<vector<int>> ans(n, vector<int> (n));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (i == j)continue;
			if (p[i][j] == 1)tree.unite(i, j);
		}
	}
	
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j) {
			if (p[i][j] == 0) {
				if (tree.connected(i, j))return 0;
			}
		}
		
	const int N = 1010;
	vector<int> g[N];
	for (int i = 0; i < n; ++i) {
		g[tree.find(i)].push_back(i);
	}
	
	for (int i = 0; i < N; ++i) {
		if (sz(g[i]) == 2)return 0;
		for (int j = 1; j < sz(g[i]); ++j) {
			ans[g[i][j]][g[i][j-1]] = 1;
			ans[g[i][j-1]][g[i][j]] = 1;
			ans[g[i][0]][g[i][sz(g[i])-1]] = 1;
			ans[g[i][sz(g[i])-1]][g[i][0]] = 1;
		}
	}
	build(ans);
	return 1;
}


//void solve() {
	//init(2, {1, 0, 1});
	//cout << compare_plants(1, 2);
//}

//int32_t main() {
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    //solve();
    //return 0;
//}

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