Submission #425523

#	Time	Username	Problem	Language	Result	Execution time	Memory
425523		p_square	Connecting Supertrees (IOI20_supertrees)	C++14	96 / 100	325 ms	24184 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

int fd_root(int a, int par[])
{
    if(par[a] == a)
        return a;

    par[a] = par[par[a]];
    return fd_root(par[a], par);
}

void merge(int a, int b, int par[])
{
    a = fd_root(a, par);
    b = fd_root(b, par);
    //cout<<a<<b<<endl;
    par[a] = b;
}

int construct(vector < vector <int> > p)
{
    int n = p.size();
    vector < vector <int> > edge;
    vector <int> empty;
    for(int i = 0; i<n; i++)
    {
        edge.push_back(empty);
        for(int j = 0; j<n; j++)
        {
            edge[i].push_back(0);
        }
    }

    int clpar[n], farpar[n];
    for(int i = 0; i<n; i++)
    {
        clpar[i] = i;
        farpar[i] = i;
    }

    for(int i = 0; i<n; i++)
    {
        for(int j = 0; j<n; j++)
        {
            if(p[i][j] != 0)
                merge(i, j, farpar);
            if(p[i][j] == 1)
                merge(i, j, clpar);
        }
    }

    bool possible = true;
    for(int i = 0; i<n; i++)
    {
        for(int j = 0; j<n; j++)
        {
            if(fd_root(i, clpar) == fd_root(j, clpar) && p[i][j] != 1)
                possible = false;

            if(fd_root(i, farpar) == fd_root(j, farpar) && p[i][j] == 0)
                possible = false;
        }
    }

    if(!possible)
        return 0;

    for(int i = 0; i<n; i++)
    {
        if(clpar[i] != i)
        {
            edge[i][clpar[i]] = 1;
            edge[clpar[i]][i] = 1;
        }
    }

    vector <int> cycle[n];

    for(int i = 0; i<n; i++)
    {
    	if(clpar[i] == i)
    	{
    		cycle[farpar[i]].push_back(i);
    	}
    }

    int u, v, z;
    for(int i = 0; i<n; i++)
    {
    	if(farpar[i] == i)
    	{
    		if(cycle[i].size() == 2)
    			possible = false;

    		if(cycle[i].size() > 2)
    		{
    			z = cycle[i].size();
    			for(int j = 0; j<z-1; j++)
    			{
    				u = cycle[i][j];
    				v = cycle[i][j+1];
    				edge[u][v] = 1;
    				edge[v][u] = 1;
    			}
    			u = cycle[i][0];
    			v = cycle[i][z-1];
    			edge[u][v] = 1;
    			edge[v][u] = 1;
    		}
    	}
    }

    if(!possible)
    	return 0;

    build(edge);
    return 1;

}

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