제출 #503200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
503200		LouayFarah	슈퍼트리 잇기 (IOI20_supertrees)	C++14	30 / 100	208 ms	22092 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 flag1 = false;
    bool flag2 = true;

    for(int i = 0; i<n; i++)
    {
        for(int j = i+1; j<n; j++)
        {
            if(p[i][j]==1)
            {
                d.join(i, j);
                flag1 = true;
            }
            if(p[i][j]==2)
            {
                d.join(i, j);
                flag2 = 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(!flag2&&flag1)
    {
        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(!flag1&&flag2)
    {
        for(int i = 0; i<n; i++)
        {
            if(groups[i].empty())
                continue;

            if(int(groups[i].size())==2)
                return 0;

            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;
            }
            int A = groups[i][len-1];
            int B = groups[i][0];

            b[A][B] = 1;
            b[B][A] = 1;
        }
    }
    else
    {
        for(auto group: groups)
        {
            if(group.empty())
                continue;


            vector<int> one, two;
            int len = int(group.size());
            for(int i = 0; i<len; i++)
            {
                int A = group[i];
                bool only2 = true;
                for(int j = 0; j<len; j++)
                {
                    if(i==j)
                        continue;
                    int B = group[j];
                    if(p[A][B]==1)
                    {
                        only2 = false;
                        break;
                    }
                }

                if(only2)
                    two.pb(i);
                else
                    one.pb(i);
            }

            if(two.empty())
            {
                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;
                }
            }
            else if(one.empty())
            {
                if(int(two.size())==2)
                    return 0;
                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;
            }
            else
            {
                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 = one[0];
                int B = two[0];
                int C = two[int(two.size())-1];

                b[A][B] = 1;
                b[B][A] = 1;
                b[A][C] = 1;
                b[C][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: 0 / 10
• Subtask 3: 19 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4