Submission #510517

#	Time	Username	Problem	Language	Result	Execution time	Memory
510517		tabr	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	241 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>>);

int construct(vector<vector<int>> p) {
    int n = (int) p.size();
    vector<int> a(n);
    iota(a.begin(), a.end(), 0);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i][j] == 1) {
                a[j] = min(a[j], i);
            }
        }
    }
    vector<vector<int>> res(n, vector<int>(n));
    vector<vector<int>> c(n);
    for (int i = 0; i < n; i++) {
        if (a[i] < i) {
            res[a[i]][i] = res[i][a[i]] = 1;
        }
        c[a[i]].emplace_back(i);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] != p[a[i]][a[j]]) {
                return 0;
            }
        }
    }
    vector<int> b(n);
    iota(b.begin(), b.end(), 0);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] == i && a[j] == j && p[i][j] == 2) {
                b[j] = min(b[j], i);
            }
        }
    }
    c = vector<vector<int>>(n);
    for (int i = 0; i < n; i++) {
        if (a[i] == i) {
            c[b[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: 0 / 19
• Subtask 4: 35 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4