Submission #527806

#	Time	Username	Problem	Language	Result	Execution time	Memory
527806		Servus2022	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	195 ms	28940 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 > G[NMAX];

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;

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);

    return;
}

void Build_type_2 ()
{
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            if(P[i][j] == 2)
                G[head[i]].push_back(head[j]), G[head[j]].push_back(head[i]), Edge[head[i]][head[j]] = Edge[head[j]][head[i]] = 1;

    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 && head[i] == head[j])
                return 0;

    for(int i = 1; i <= N; ++i)
        if(i != head[i])
            Edge[i][head[i]] = Edge[head[i]][i] = 1;

    Build_type_2();

    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: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4