Submission #399608

#	Time	Username	Problem	Language	Result	Execution time	Memory
399608		luisgalan	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	275 ms	24092 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e3 + 3;

int parent[MAX_N];
int find(int x) {
    return parent[x] = (parent[x] == x ? x : find(parent[x]));
}
void connect(int a, int b) {
    if (rand() % 2) swap(a, b);
    parent[find(a)] = find(b);
}

int construct(std::vector<std::vector<int>> p) {
    int n = p.size();
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
    vector<vector<int>> result(n);
    fill(result.begin(), result.end(), vector<int>(n));
    if (n == 1) {
        build(result);
        return 1;
    }
    bool valid = true;
    for (int i = 0; i < n; i++) {
        if (!valid) break;
        for (int j = 0; j < n; j++) {
            if (p[i][j]) {
                if (find(i) == find(j)) continue;
                connect(i, j);
                result[i][j] = 1;
                result[j][i] = 1;
            } else {
                if (find(i) == find(j)) {
                    valid = false;
                    break;
                }
            }
        }
    }

    if (valid) {
        build(result);
    }
    return valid;
}

// subtask 2
// answer consists of a set of different paths
// since p[i][j] is 0 or 1 all pairs with a 1 are
// part of the same component
// also need to check if impossible now

// we do two passes
// first build UFDS
// then check if UFDS holds

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