Submission #510568

#	Time	Username	Problem	Language	Result	Execution time	Memory
510568		tabr	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	325 ms	22104 KiB

supertrees

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

void build(vector<vector<int>>);

struct dsu {
    vector<int> p;
    vector<int> sz;
    int n;

    dsu(int _n) : n(_n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
        sz.assign(n, 1);
    }

    inline int get(int x) {
        if (p[x] == x) {
            return x;
        } else {
            return p[x] = get(p[x]);
        }
    }

    inline bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            swap(x, y);
        }
        p[x] = y;
        sz[y] += sz[x];
        return true;
    }

    inline bool same(int x, int y) {
        return (get(x) == get(y));
    }
};

int construct(vector<vector<int>> p) {
    int n = (int) p.size();
    dsu uf1(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i][j] == 3) {
                return 0;
            }
            if (p[i][j] == 1) {
                uf1.unite(i, j);
            }
        }
    }
    vector<vector<int>> res(n, vector<int>(n));
    vector<vector<int>> c(n);
    for (int i = 0; i < n; i++) {
        c[uf1.get(i)].emplace_back(i);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < (int) c[i].size(); j++) {
            res[c[i][0]][c[i][j]] = res[c[i][j]][c[i][0]] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i][j] != p[uf1.get(i)][uf1.get(j)]) {
                return 0;
            }
        }
    }
    dsu uf2(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (uf1.get(i) == i && uf1.get(j) == j && p[i][j] == 2) {
                uf2.unite(i, j);
            }
        }
    }
    c = vector<vector<int>>(n);
    for (int i = 0; i < n; i++) {
        if (uf1.get(i) == i) {
            c[uf2.get(i)].emplace_back(i);
        }
    }
    for (int i = 0; i < n; i++) {
        int sz = (int) c[i].size();
        if (sz == 0 || sz == 1) {
            continue;
        }
        if (sz == 2) {
            return 0;
        }
        for (int j = 0; j < sz; j++) {
            res[c[i][j]][c[i][(j + 1) % sz]] = res[c[i][(j + 1) % sz]][c[i][j]] = 1;
        }
        for (int x = 0; x < sz; x++) {
            for (int y = x + 1; y < sz; y++) {
                if (p[c[i][x]][c[i][y]] != 2) {
                    return 0;
                }
            }
        }
    }
    build(res);
    return 1;
}

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