Submission #1245227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245227		qwusha	Connecting Supertrees (IOI20_supertrees)	C++20	0 / 100	1 ms	328 KiB

supertrees

#include "supertrees.h"

#include <iostream>
#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

int inf = 1e9 + 7;


struct dsu {
    vector<int> par;
    vector<int> sz;
    void init(int n) {
        par.assign(n, 0);
        sz.assign(n, 1);
        for (int i = 0; i < n; i++) {
            par[i] = i;
        }
    }
    int get_par(int v) {
        if (par[v] == v) {
            return v;
        }
        int ans = get_par(par[v]);
        par[v] = ans;
        return ans;
    }
    void unitik(int v, int u) {
        v = get_par(v);
        u = get_par(u);
        if (sz[v] < sz[u]) {
            swap(v, u);
        }
        sz[v] += sz[u];
        par[u] = v;
    }
};


int construct(vector<vector<int>> p) {
    int n = p.size();
    dsu dsu;
    dsu.init(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i][j] > 0 && dsu.get_par(i) != dsu.get_par(j)) {
                dsu.unitik(i, j);
            }
        }
    }
    bool ok = 1;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i][j] == 0 && dsu.get_par(i) == dsu.get_par(j)) {
                ok = 0;
            }
        }
    }
    if (!ok) {
        return 0;
    }
    vector<vector<int>> b(n, vector<int>(n));
    vector<vector<int>> gr(n);
    for (int i = 0; i < n; i++) {
        gr[dsu.get_par(i)].push_back(i);
    }
    for (auto g : gr) {
        for (int i = 0; i < g.size() - 1; i++) {
            b[g[i]][g[i + 1]] = 1;
            b[g[i + 1]][g[i]] = 1;
        }
    }
    build(b);
    return 1;

}

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