Submission #779165

#	Time	Username	Problem	Language	Result	Execution time	Memory
779165		kamelfanger83	Connecting Supertrees (IOI20_supertrees)	C++17	46 / 100	161 ms	23976 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <cassert>

using namespace std;

int construct(vector<vector<int>> p) {
    int n = p.size();
    vector<vector<int>> res (n);
    vector<bool> inc (n);

    for (int i = 0; i < n; ++i) {
        if (!res[i].empty()) continue;
        res[i].assign(n, 0);
        inc[i] = true;
        for (int j = 0; j < n; ++j) {
            if (p[i][j] == 0 || i == j) continue;
            if (p[i][j] == 1){
                res[j].assign(n, 0);
                res[j][i] = 1;
                res[i][j] = 1;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if (!inc[i]) continue;
        int ft = -1, lt = -1, bt = -1, at = -1;
        for (int j = 0; j < n; ++j) {
            if (p[i][j] == 2 && inc[j]){
                if (ft == -1) ft = j;
                if (j < i) bt = j;
                if (j > i && at == -1) at = j;
                lt = j;
            }
        }
        if (lt == -1) continue;
        if (at == -1) at = ft;
        if (bt == -1) bt = lt;
        res[i][bt] = 1;
        res[i][at] = 1;
    }

    build(res);
    return 1;
}

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