Submission #388499

#	Time	Username	Problem	Language	Result	Execution time	Memory
388499		alexxela12345	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	294 ms	26120 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <numeric>
#include <algorithm>
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] == 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++) {
        vector<int> arr = {i};
        bool bad = 0;
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 2) {
                if (get(i) == get(j)) {
                    bad = 1;
                    break;
                }
                arr.push_back(j);
            }
        }
        if (bad || arr.size() == 1)
            continue;
        if (arr.size() == 2) {
            return 0;
        }
        for (int &el : arr) {
            el = get(el);
        }
        sort(arr.begin(), arr.end());
        arr.resize(unique(arr.begin(), arr.end()) - arr.begin());
        vector<vector<int>> comps;
        for (auto el : arr) {
            comp.clear();
            dfs(el);
            cur_time++;
            comps.push_back(comp);
        }
        for (int i = 0; i < (int) comps.size(); i++) {
            for (int j = i + 1; j < (int) comps.size(); j++) {
                for (int el1 : comps[i]) {
                    for (int el2 : comps[j]) {
                        p2[el1][el2] = p2[el2][el1] = 2;
                    }
                }
            }
        }
        for (int i = 0; i < (int) arr.size(); i++) {
            int a = arr[i];
            int b = arr[(i + 1) % arr.size()];
            merge(a, b);
            answer[a][b] = answer[b][a] = 1;
        }
    }
    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: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4