Submission #301603

#	Time	Username	Problem	Language	Result	Execution time	Memory
301603		smax	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	292 ms	26104 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <queue>
#include <set>
using namespace std;

struct DSU {
    vector<int> par, sz;

    DSU(int n) : par(n), sz(n) {
        for (int i=0; i<n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int findRoot(int u) {
        if (par[u] != u)
            par[u] = findRoot(par[u]);
        return par[u];
    }

    bool unite(int u, int v) {
        u = findRoot(u), v = findRoot(v);
        if (u == v)
            return false;
        if (sz[u] < sz[v])
            swap(u, v);
        par[v] = u;
        sz[u] += sz[v];
        return true;
    }
};

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}

	vector<vector<int>> adj(n);
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++) {
            if (p[i][j] == 3)
                return 0;
            if (p[i][j] == 1)
                adj[i].push_back(j);
        }

    vector<int> id(n, -1);
    vector<vector<int>> comp;
    queue<int> q;
    for (int i=0; i<n; i++)
        if (id[i] == -1) {
            comp.emplace_back();
            q.push(i);
            id[i] = (int) comp.size() - 1;
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                for (int v : comp.back())
                    if (p[u][v] != 1)
                        return 0;
                comp.back().push_back(u);
                for (int v : adj[u])
                    if (id[v] == -1) {
                        q.push(v);
                        id[v] = (int) comp.size() - 1;
                    }
            }
        }

    int m = comp.size();
    DSU ds(m);
    vector<vector<bool>> two(m, vector<bool>(m));
    for (int i=0; i<m; i++) {
        for (int j=1; j<(int)comp[i].size(); j++)
            answer[comp[i][j-1]][comp[i][j]] = answer[comp[i][j]][comp[i][j-1]] = 1;
        for (int u : comp[i])
            for (int v=0; v<n; v++)
                if (p[u][v] == 2) {
                    two[id[u]][id[v]] = two[id[v]][id[u]] = true;
                    ds.unite(id[u], id[v]);
                }
    }

    vector<vector<int>> big(m);
    for (int i=0; i<m; i++) {
        for (int v : big[ds.par[i]])
            if (!two[i][v])
                return 0;
        big[ds.par[i]].push_back(i);
    }

    auto get = [&] (int id) {
        return comp[id][0];
    };

    for (auto &c : big) {
        if (c.size() == 2)
            return 0;
        for (int i=1; i<(int)c.size(); i++)
            answer[get(c[i-1])][get(c[i])] = answer[get(c[i])][get(c[i-1])] = 1;
        if (c.size() > 2)
            answer[get(c.back())][get(c[0])] = answer[get(c[0])][get(c.back())] = 1;
    }

	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