Submission #527861

#	Time	Username	Problem	Language	Result	Execution time	Memory
527861		Servus2022	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	332 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e3 + 1;

int N;
int P[NMAX][NMAX];

int head[NMAX];

bool Edge[NMAX][NMAX];

vector < int > roots;

vector < int > List[NMAX];

bool OK = 1;

class DisjointSets
{
    int T[NMAX], Size[NMAX];

private:
    inline int Find (int X)
    {
        if(X == T[X])
            return X;

        return (T[X] = Find(T[X]));
    }

    inline void my_swap (int &x, int &y)
    {
        x = (x ^ y), y = (x ^ y), x = (x ^ y);

        return;
    }

public:
    inline void Initialize (int N)
    {
        for(int i = 1; i <= N; ++i)
            T[i] = i, Size[i] = 1;

        return;
    }

    inline bool Unify (int X, int Y)
    {
        X = Find(X), Y = Find(Y);

        if(X == Y)
            return 0;

        if(Size[X] < Size[Y])
            my_swap(X, Y);

        Size[X] += Size[Y], Size[Y] = 0;
        T[Y] = X;

        return 1;
    }

    inline int Who_is_the_boss (int Node)
    {
        return Find(Node);
    }
} DSU, cycles;

void Build_type_1 ()
{
    DSU.Initialize(N);

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            if(P[i][j] == 1)
                DSU.Unify(i, j);

    for(int i = 1; i <= N; ++i)
    {
        head[i] = DSU.Who_is_the_boss(i);

        if(i == head[i])
            roots.push_back(i);
        else
            Edge[i][head[i]] = Edge[head[i]][i] = 1;
    }

    return;
}

void Build_type_2 ()
{
    cycles.Initialize(N);

    for(int i = 0; i < (int)roots.size() - 1; ++i)
        for(int j = i + 1; j < (int)roots.size(); ++j)
            if(P[roots[i]][roots[j]] == 2)
                cycles.Unify(roots[i], roots[j]);

    for(auto it : roots)
    {
        int rep = cycles.Who_is_the_boss(it);

        List[rep].push_back(it);
    }

    for(int i = 1; i <= N; ++i)
        if((int)List[i].size() > 2)
        {
            for(int j = 0; j < (int)List[i].size() - 1; ++j)
                Edge[List[i][j]][List[i][j + 1]] = Edge[List[i][j + 1]][List[i][j]] = 1;

            int First = List[i][0];
            int Last = List[i][(int)List[i].size() - 1];

            Edge[First][Last] = Edge[Last][First] = 1;
        }
        else if((int)List[i].size() == 1 || (int)List[i].size() == 2)
            OK = 0;

    return;
}

int construct (vector < vector < int > > p)
{
    N = (int)p.size();

    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
        {
            P[i + 1][j + 1] = p[i][j];

            if(p[i][j] == 3)
                return 0;
        }

    Build_type_1();

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            if(P[i][j] == 0)
                if(head[i] == head[j])
                    return 0;

    Build_type_2();

    if(!OK)
        return 0;

    ///
    vector < vector < int > > ans;
    for(int i = 0; i < N; ++i)
    {
        vector < int > _temp;

        for(int j = 0; j < N; ++j)
            if(Edge[i + 1][j + 1])
                _temp.push_back(1);
            else
                _temp.push_back(0);
        ans.push_back(_temp);
    }
    build(ans);
    ///

    return 1;
}

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