Submission #510489

#	Time	Username	Problem	Language	Result	Execution time	Memory
510489		tabr	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	366 ms	24048 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++) {
            p[c[i][j]][c[i][(j + 1) % sz]] = p[c[i][(j + 1) % sz]][c[i][j]] = 1;
        }
    }
    build(res);
    return 1;
}

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