Submission #527839

#	Time	Username	Problem	Language	Result	Execution time	Memory
527839		Servus2022	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	188 ms	28996 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;

vector < int > List[NMAX];

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), List[head[i]].push_back(i);

    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)
        if(!List[i].empty())
            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;

    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;

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            if(P[i][j] == 2)
                {
                    int x1 = List[head[i]][0], x2 = List[head[j]][0];
                    int y1 = List[head[i]][(int)List[head[i]].size() - 1], y2 = List[head[j]][(int)List[head[j]].size() - 1];

                    Edge[x1][x2] = Edge[x2][x1] = 1;
                    Edge[y1][y2] = Edge[y2][y1] = 1;
                }

    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