Submission #300247

#	Time	Username	Problem	Language	Result	Execution time	Memory
300247		daniel920712	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	277 ms	22392 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <stdio.h>
using namespace std;
vector < int > how[1005];
vector < int > how2[1005];
vector < int > cycle;
int Father[1005];
int Find(int here)
{
    if(Father[here]==here) return here;
    Father[here]=Find(Father[here]);
    return Father[here];
}
int construct(vector < vector< int > > p)
{
	int n=p.size(),i,j,k,m;
	vector< vector<int> > answer;
	vector< int > row;
	for(i=0;i<n;i++) row.push_back(0);
	for(i=0;i<n;i++)
    {
        answer.push_back(row);
        Father[i]=i;
    }
	for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(p[i][j]==3) return 0;
            if(p[i][j]==0&&Find(i)==Find(j)) return 0;
            else if(p[i][j]) Father[Find(i)]=Find(j);
        }
    }
    for(i=0;i<n;i++) how[Find(i)].push_back(i);
    for(i=0;i<n;i++)
    {
        m=how[i].size();
        if(m<=1) continue;
        for(auto j:how[i]) Father[j]=j;
        for(j=0;j<m;j++)
        {
            for(k=0;k<m;k++)
            {
                if(Find(how[i][j])==Find(how[i][k])&&p[how[i][j]][how[i][k]]==2) return 0;
                else if(p[how[i][j]][how[i][k]]==1) Father[Find(how[i][k])]=Find(how[i][j]);
            }
        }
        for(auto j:how[i]) how2[Find(j)].push_back(j);
        cycle.clear();
        for(auto j:how[i])
        {
            m=how2[j].size();
            if(m==0) continue;
            for(k=1;k<m;k++)
            {
                answer[how2[j][k-1]][how2[j][k]]=1;
                answer[how2[j][k]][how2[j][k-1]]=1;
            }
            cycle.push_back(how2[j][0]);
        }
        m=cycle.size();
        if(m==2) return 0;
        if(m<=1) continue;
        for(j=1;j<m;j++)
        {
            answer[cycle[j-1]][cycle[j]]=1;
            answer[cycle[j]][cycle[j-1]]=1;
        }
        answer[cycle[m-1]][cycle[0]]=1;
        answer[cycle[0]][cycle[m-1]]=1;
    }
	build(answer);
	return 1;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
*/

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