Submission #502974

#	Time	Username	Problem	Language	Result	Execution time	Memory
502974		LouayFarah	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	212 ms	22436 KiB

supertrees

#include "bits/stdc++.h"

using namespace std;

#define endl "\n"
#define ll long long int
#define pb push_back
#define mp make_pair
#define fi first
#define se second

const long long MOD = 1e9+7;
const long long INF = 1e18;

int nx[4] = {0, 0, -1, 1};
int ny[4] = {1, -1, 0, 0};

void build(vector<vector<int>> b);

struct dsu
{
    vector<int> len;
    vector<int> link;

    void init(int n)
    {
        len.assign(n, 1);
        link.assign(n, 0);
        for(int i = 0; i<n; i++)
        {
            link[i] = i;
        }
    }

    int search(int x)
    {
        if(x!=link[x])
            link[x] = search(link[x]);
        return link[x];
    }

    bool check(int a, int b)
    {
        return search(a)==search(b);
    }

    void join(int a, int b)
    {
        a = search(a);
        b = search(b);

        if(a!=b)
        {
            if(len[a]<len[b])
                swap(a, b);

            len[a]+=len[b];
            link[b] = a;
        }
    }
};

int construct(vector<vector<int>> p)
{
    int n = int(p[0].size());

    vector<vector<int>> b(n, vector<int>(n, 0));

    dsu d;
    d.init(n);

    bool flag = false;

    for(int i = 0; i<n; i++)
    {
        for(int j = i+1; j<n; j++)
        {
            if(p[i][j]==1)
                d.join(i, j);
            if(p[i][j]==2)
            {
                d.join(i, j);
                flag = true;
            }
        }
    }

    vector<vector<int>> groups(n);
    for(int i = 0; i<n; i++)
    {
        int parent = d.search(i);
        groups[parent].pb(i);
    }

    /*for(int i = 0; i<n; i++)
    {
        cout << i << ": ";
        for(auto elt: groups[i])
            cout << elt << ' ';
        cout << endl;
    }*/


    if(!flag)
    {
        for(int i = 0; i<n; i++)
        {
            if(groups[i].empty())
                continue;

            int len = int(groups[i].size());
            for(int j = 0; j<len-1; j++)
            {

                int A = groups[i][j];
                int B = groups[i][j+1];

                b[A][B] = 1;
                b[B][A] = 1;
            }
        }
    }
    else
    {
        for(int i = 0; i<n; i++)
        {
            if(groups[i].empty())
                continue;

            int len = int(groups[i].size());
            vector<int> one, two;
            vector<bool> visited(n, false);
            for(int j = 0; j<len; j++)
            {
                for(int k = j+1; k<len; k++)
                {
                    int A = groups[i][j];
                    int B = groups[i][k];

                    if(p[A][B]==1)
                    {
                        if(!visited[A])
                        {
                            one.pb(A);
                            visited[A] = true;
                        }
                        if(!visited[B])
                        {
                            one.pb(B);
                            visited[B] = true;
                        }
                    }
                    if(p[A][B]==2)
                    {
                        if(!visited[A])
                        {
                            two.pb(A);
                            visited[A] = true;
                        }
                        if(!visited[B])
                        {
                            two.pb(B);
                            visited[B] = true;
                        }
                    }
                }
            }

            if(int(one.size())==len)
            {
                for(int i = 0; i<n; i++)
                {
                    if(groups[i].empty())
                        continue;

                    int len = int(groups[i].size());
                    for(int j = 0; j<len-1; j++)
                    {

                        int A = groups[i][j];
                        int B = groups[i][j+1];

                        b[A][B] = 1;
                        b[B][A] = 1;
                    }
                }
            }
            else
            {
                if(int(two.size()==2))
                    return 0;
                for(int j = 0; j<int(one.size())-1; j++)
                {
                    int A = one[j];
                    int B = one[j+1];

                    b[A][B] = 1;
                    b[B][A] = 1;
                }
                for(int j = 0; j<int(two.size())-1; j++)
                {
                    int A = two[j];
                    int B = two[j+1];

                    b[A][B] = 1;
                    b[B][A] = 1;
                }

                int A = two[int(two.size())-1];
                int B = two[0];

                b[A][B] = 1;
                b[B][A] = 1;

            }
        }
    }

    for(int i = 0; i<n; i++)
    {
        for(int j = i+1; j<n; j++)
        {
            if(p[i][j]==0&&d.check(i, j))
                return 0;
            if(!d.check(i, j)&&p[i][j]!=0)
                return 0;
        }
    }

    for(int i = 0; i<n; i++)
    {
        b[i][i]  = 0;
    }

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