Submission #388485

#	Time	Username	Problem	Language	Result	Execution time	Memory
388485		alexxela12345	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	303 ms	26104 KiB

supertrees

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

using namespace std;

const int MAXN = 1e3;

int pa[MAXN];
int ra[MAXN];

void init() {
    iota(pa, pa + MAXN, 0);
    fill(ra, ra + MAXN, 0);
}

int get(int a) {
    if (a == pa[a])
        return a;
    return pa[a] = get(pa[a]);
}

void merge(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b)
        return;
    if (ra[b] > ra[a])
        swap(a, b);
    pa[b] = a;
    if (ra[a] == ra[b])
        ra[a]++;
}

vector<vector<int>> g;

vector<vector<int>> p2;

vector<int> comp;
vector<int> used;

int cur_time = 1;

void dfs(int v) {
    used[v] = cur_time;
    comp.push_back(v);
    for (int u : g[v]) {
        if (used[u] < cur_time) {
            dfs(u);
        }
    }
}

int construct(vector<vector<int>> p) {
    init();
    int n = p.size();
    used.resize(n);
    g.resize(n);
    p2.resize(n, vector<int> (n));
    vector<vector<int>> answer;
    for (int i = 0; i < n; i++) {
        vector<int> row;
        row.resize(n);
        answer.push_back(row);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 3)
                return 0;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 1) {
                if (get(i) != get(j)) {
                    merge(i, j);
                    comp.clear();
                    dfs(i);
                    cur_time++;
                    auto c1 = comp;
                    comp.clear();
                    dfs(j);
                    cur_time++;
                    auto c2 = comp;
                    for (int el1 : c1) {
                        for (int el2 : c2) {
                            p2[el2][el1] = 1;
                            p2[el1][el2] = 1;
                        }
                    }
                    g[i].push_back(j);
                    g[j].push_back(i);
                    answer[i][j] = 1;
                    answer[j][i] = 1;
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 2) {
            }
        }
    }
    for (int i = 0; i < n; i++) {
        p2[i][i] = 1;
    }
    if (p != p2) {
        return 0;
    }
    build(answer);
    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