Submission #1076321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076321		juicy	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	176 ms	24180 KiB

supertrees

#include "supertrees.h"

#include <bits/stdc++.h>

int construct(std::vector<std::vector<int>> p) {
    int n = p.size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (p[i][j] == 3) {
                return 0;
            }
        }
    }
    std::vector<bool> root(n);
    std::vector res(n, std::vector<int>(n));
    auto add = [&](int u, int v) {
        res[u][v] = res[v][u] = 1;
    };
    for (int i = 0; i < n; ++i) {
        int j = 0;
        while (p[i][j] ^ 1) {
            ++j;
        }
        if (j == i) {
            root[i] = 1;
        } else {
            if (p[i] != p[j]) {
                return 0;
            }
            add(i, j);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (root[i]) {
            int j = 0;
            while (!p[i][j]) {
                ++j;
            }
            for (int k = 0; k < n; ++k) {
                if ((p[i][k] != 0) != (p[j][k] != 0)) {
                    return 0;
                }
            }
            if (j == i) {
                int lst = i;
                for (int k = j + 1; k < n; ++k) {
                    if (root[k] && p[i][k]) {
                        add(lst, k);
                        lst = k;
                    }
                }
                if (lst != i) {
                    if (res[lst][i]) {
                        return 0;
                    }
                    add(lst, 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