Submission #1245378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245378		qwusha	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	120 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) {
    cout << "possible " << endl;
    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();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 3)
                return 0;
        }
    }
    dsu dsubig;
    dsubig.init(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i][j] > 0 && dsubig.get_par(i) != dsubig.get_par(j)) {
                dsubig.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 && dsubig.get_par(i) == dsubig.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[dsubig.get_par(i)].push_back(i);
    }

    dsu grdsu;
    map<int, vector<int>> mp;
    for (int j = 0; j < n; j++) {
        if (gr[j].size() < 2)
            continue;
        grdsu.init(gr[j].size());
        mp.clear();
        for (int i = 0; i < gr[j].size(); i++) {
            for (int q = i + 1; q < gr[j].size(); q++) {
                if (p[gr[j][i]][gr[j][q]] == 1 && grdsu.get_par(i) != grdsu.get_par(q)) {
                    grdsu.unitik(i, q);
                }
            }
        }
        bool ch = 1;
        for (int i = 0; i < gr[j].size(); i++) {
            for (int q = i + 1; q < gr[j].size(); q++) {
                if (p[gr[j][i]][gr[j][q]] == 2 && grdsu.get_par(i) == grdsu.get_par(q)) {
                    ch = 0;
                }
            }
        }
        if (!ch)
            return 0;
        for (int i = 0; i < gr[j].size(); i++) {
            mp[grdsu.get_par(i)].push_back(i);
        }
        vector<int> bosses;
        for (auto [boss, ve] : mp) {
            bosses.push_back(boss);
            for (int i = 0; i < ve.size() - 1; i++) {
                b[gr[j][ve[i]]][gr[j][ve[i + 1]]] = 1;
                b[gr[j][ve[i + 1]]][gr[j][ve[i]]] = 1;
            }
        }
        if (bosses.size() == 1) {
            continue;
        }
        if (bosses.size() == 2) {
            return 0;
        }
        for (int i = 0; i < bosses.size(); i++) {
            b[gr[j][bosses[i]]][gr[j][bosses[(i + 1) % bosses.size()]]] = 1;
            b[gr[j][bosses[(i + 1) % bosses.size()]]][gr[j][bosses[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: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4