Submission #1245235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245235		qwusha	Connecting Supertrees (IOI20_supertrees)	C++20	19 / 100	114 ms	22244 KiB

supertrees

#include "supertrees.h"

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

#define fi first
#define se second

using namespace std;

int inf = 1e9 + 7;

/*
void build(vector<vector<int>> b) {
    int n = b.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (b[i][j] == 1) {
                cout << i << ' ' << j << endl;
            }
        }
    }
}*/


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 (int j = 0; j < n; j++) {
        if (gr[j].size() < 2)
            continue;
        if (gr[j].size() == 2)
            return 0;
        for (int i = 0; i < gr[j].size(); i++) {
            b[gr[j][i]][gr[j][(i + 1) % gr[j].size()]] = 1;
            b[gr[j][(i + 1) % gr[j].size()]][gr[j][i]] = 1;
        }
    }
    build(b);
    return 1;

}
/*
int main() {
    int n;
    cin >> n;
    vector<vector<int>> w(n, vector<int> (n, 1));
    int va = construct(w);
}*/

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