Submission #403866

#	Time	Username	Problem	Language	Result	Execution time	Memory
403866		SamAnd	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	432 ms	27368 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
typedef long long ll;
const int N = 1003;

int n;
vector<vector<int> > p;

bool c[N];

vector<int> v;
void dfs(int x)
{
    if (c[x])
        return;
    c[x] = true;
    v.push_back(x);
    for (int h = 0; h < n; ++h)
    {
        if (p[x][h])
        {
            dfs(h);
        }
    }
}

vector<vector<int> > vv;
bool cc[N];
vector<int> vs;
void dfss(int x)
{
    if (cc[x])
        return;
    cc[x] = true;
    vs.push_back(x);
    for (int h = 0; h < n; ++h)
    {
        if (p[x][h] == 1)
        {
            dfss(h);
        }
    }
}

int construct(vector<vector<int> > p)
{
    ::p = p;
	n = p.size();
    vector<vector<int> > ans;
	for (int i = 0; i < n; i++)
    {
		vector<int> row;
		row.resize(n);
		ans.push_back(row);
	}

	for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (p[i][j] == 3)
                return 0;
        }
    }

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

    for (int i = 0; i < n; ++i)
    {
        if (!c[i])
        {
            v.clear();
            dfs(i);
            for (int i = 0; i < sz(v); ++i)
            {
                for (int j = 0; j < sz(v); ++j)
                {
                    if (!p[v[i]][v[j]])
                        return 0;
                }
            }

            vv.clear();
            for (int i = 0; i < sz(v); ++i)
            {
                if (!cc[v[i]])
                {
                    vs.clear();
                    dfss(v[i]);
                    for (int i = 0; i < sz(vs); ++i)
                    {
                        for (int j = 0; j < sz(vs); ++j)
                        {
                            if (p[vs[i]][vs[j]] != 1)
                                return 0;
                        }
                    }
                    vv.push_back(vs);
                }
            }

            for (int i = 0; i < sz(vv); ++i)
            {
                for (int j = 0; j < sz(vv[i]) - 1; ++j)
                {
                    ans[vv[i][j]][vv[i][j + 1]] = 1;
                }
            }
            if (sz(vv) != 1)
                for (int i = 0; i < sz(vv); ++i)
                    ans[vv[i][0]][vv[(i + 1) % sz(vv)][0]] = 1;
        }
    }

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (ans[i][j] == 1)
                ans[j][i] = 1;
        }
    }

    build(ans);
    return 1;
}

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