Submission #1265390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265390		BlockOG	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	148 ms	22284 KiB

supertrees

#include <bits/stdc++.h>

// mrrrow meeow :3
// go play vivid/stasis now! it's free on steam

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = [] {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

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

bool erased[1000];
int dsu[1000];
set<int> comps[1000];

int get(int i) {
    if (dsu[i] == i) return i;
    return dsu[i] = get(dsu[i]);
}

void merge(int i, int j) {
    i = get(i), j = get(j);
    if (i == j) return;

    if (comps[i].size() > comps[j].size()) swap(i, j);
    dsu[i] = j;
    for (int k : comps[i]) comps[j].insert(k);
    comps[i].clear();
}

int construct(vector<vector<int>> p) {
    int n = p.size();
    fo(i, 0, n) dsu[i] = i, comps[i] = {i};
    vector<vector<int>> res(n, vector<int>(n));

    fo(i, 0, n) {
        fo(j, 0, n) {
            if (p[i][j] == 3) return 0;
            else if (p[i][j]) {
                merge(i, j);
                if (i != j && p[i][j] == 1 && !erased[i] && !erased[j]) {
                    if (p[i] != p[j]) return 0;

                    comps[get(j)].erase(j);
                    erased[j] = true;
                    res[i][j] = res[j][i] = 1;
                }
            }
        }
    }

    fo(i, 0, n) {
        fo(j, 0, n) {
            if (p[i][j] == 0 && get(i) == get(j)) return 0;
        }
    }

    fo(i, 0, n) {
        if (comps[i].size() <= 1) continue;
        if (comps[i].size() == 2) return 0;

        int j = *comps[i].rbegin();
        for (int i : comps[i]) {
            res[i][j] = res[j][i] = 1;
            j = i;
        }
    }

    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