Submission #705788

#	Time	Username	Problem	Language	Result	Execution time	Memory
705788		finn__	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	238 ms	24072 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

struct Dsu
{
    vector<int64_t> t;

    Dsu(size_t n) { t = vector<int64_t>(n, -1); }

    int64_t repr(int64_t u) { return t[u] < 0 ? u : t[u] = repr(t[u]); }

    void merge(int64_t u, int64_t v)
    {
        u = repr(u);
        v = repr(v);
        if (u == v)
            return;

        if (t[u] > t[v])
            swap(u, v);
        t[u] += t[v];
        t[v] = u;
    }

    bool same_set(int64_t u, int64_t v) { return repr(u) == repr(v); }
};

int construct(vector<vector<int>> p)
{
    Dsu connected(p.size()), one_connected(p.size());

    for (size_t i = 0; i < p.size(); i++)
        for (size_t j = 0; j < p.size(); j++)
        {
            if (p[i][j] == 3)
                return 0;
            if (p[i][j])
                connected.merge(i, j);
            if (p[i][j] == 1)
                one_connected.merge(i, j);
        }

    for (size_t i = 0; i < p.size(); i++)
        for (size_t j = 0; j < p.size(); j++)
        {
            if ((p[i][j] == 0 && connected.same_set(i, j)) ||
                (p[i][j] != 0 && !connected.same_set(i, j)))
                return 0;
            if ((p[i][j] == 1 && !one_connected.same_set(i, j)) ||
                (p[i][j] != 1 && one_connected.same_set(i, j)))
                return 0;
            if ((p[i][j] == 2 && !(connected.same_set(i, j) && !one_connected.same_set(i, j))) ||
                (p[i][j] != 2 && connected.same_set(i, j) && !one_connected.same_set(i, j)))
                return 0;
        }

    vector<vector<int>> adj(p.size(), vector<int>(p.size(), 0));
    vector<vector<size_t>> roots(p.size());
    vector<bool> visited(p.size(), 0);

    for (size_t i = 0; i < p.size(); i++)
        if (!visited[i])
        {
            visited[i] = 1;
            roots[connected.repr(i)].push_back(i);
            for (size_t j = 0; j < p.size(); j++)
                if (j != i && one_connected.same_set(i, j))
                {
                    adj[i][j] = adj[j][i] = 1;
                    visited[j] = 1;
                }
        }
    for (auto const &v : roots)
    {
        if (v.size() > 1)
            for (size_t i = 0; i < v.size(); i++)
                adj[v[i]][v[(i + 1) % v.size()]] = adj[v[(i + 1) % v.size()]][v[i]] = 1;
        if (v.size() == 2)
            return 0;
    }

    build(adj);
    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