Submission #1265255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265255		canhnam357	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	119 ms	22376 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu {
    vector<int> par;
    vector<vector<int>> cc;
    dsu(int n) {
        par.resize(n);
        cc.resize(n);
        for (int i = 0; i < n; i++) cc[i].push_back(i);
        iota(par.begin(), par.end(), 0);
    }
    int find(int u) {
        return u == par[u] ? u : par[u] = find(par[u]);
    }
    void join(int a, int b) {
        a = find(a), b = find(b);
        if (a != b) {
            if (cc[a].size() > cc[b].size()) swap(a, b);
            par[a] = b;
            for (int i : cc[a]) cc[b].push_back(i);
        }
    }
};
int construct(vector<vector<int>> p) {
    int n = p.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 3) return 0;
        }
    }
    dsu e1(n), e(n), e2(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i][j] == 1) e1.join(i, j);
            if (p[i][j] == 2) e2.join(i, j);
            if (p[i][j]) e.join(i, j);
        }
    }
    for (int i = 0; i < n; i++) {
        if (e.par[i] == i) {
            for (int a : e.cc[i]) {
                for (int b : e.cc[i]) {
                    if (!p[a][b]) return 0;
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (e1.par[i] == i) {
            for (int a : e1.cc[i]) {
                for (int b : e1.cc[i]) {
                    if (p[a][b] != 1) return 0;
                }
            }
        }
    }
    vector<pair<int, int>> edge;
    for (int i = 0; i < n; i++) {
        if (e1.par[i] == i) {
            for (int j = 1; j < e1.cc[i].size(); j++) {
                edge.emplace_back(e1.cc[i][j - 1], e1.cc[i][j]);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (e2.par[i] == i) {
            set<int> s;
            for (int j : e2.cc[i]) {
                s.insert(e1.find(j));
            }
            if (s.size() == 2) return 0;
            if (s.size() == 1) continue;
            vector<int> v(s.begin(), s.end());
            for (int j = 0; j < v.size(); j++) {
                edge.emplace_back(v[j], v[(j + 1) % v.size()]);
            }
        }
    }
    vector<vector<int>> res(n, vector<int>(n));
    for (auto [u, v] : edge) res[u][v] = res[v][u] = 1;
    build(res);
    return 1;
}
// int main() {}

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