제출 #1315133

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315133		yusifm	슈퍼트리 잇기 (IOI20_supertrees)	C++20	0 / 100	1 ms	332 KiB

supertrees

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int sz=1001,INF=1000000000;
vector<int>parent(sz,-1),Parent(sz,-1);
int get(int num)
{
    if(parent[num]<0)
    {
        return num;
    }
    else
    {
        parent[num]=get(parent[num]);
        return get(parent[num]);
    }
}
void unite(int num1,int num2)
{
    int res1=get(num1),res2=get(num2);
    if(res1!=res2)
    {
        if(parent[res1]>parent[res2])
        {
            swap(res1,res2);
        }
        parent[res1]+=parent[res2],parent[res2]=res1;
    }
}
int Get(int num)
{
    if(Parent[num]<0)
    {
        return num;
    }
    else
    {
        Parent[num]=Get(Parent[num]);
        return Get(Parent[num]);
    }
}
void Unite(int num1,int num2)
{
    int res1=Get(num1),res2=Get(num2);
    if(res1!=res2)
    {
        if(Parent[res1]>Parent[res2])
        {
            swap(res1,res2);
        }
        Parent[res1]+=Parent[res2],Parent[res2]=res1;
    }
}
int construct(vector<vector<int>>nums)
{
	vector<int>deg(nums.size()+1,0);
	vector<vector<int>>ans(nums.size(),vector<int>(nums.size(),0));
	for(int i=0;i<nums.size();i++)
	{
		for(int j=0;j<nums.size();j++)
		{
			if(nums[i][j]==2)
			{
				unite(i,j);
			}
		}
	}
	for(int i=0;i<nums.size();i++)
	{
		for(int j=0;j<nums.size();j++)
		{
			if(nums[i][j]==0)
			{
				if(get(i)==get(j))
				{
					return 0;
				}
			}
		}
	}
	for(int i=0;i<nums.size();i++)
	{
		for(int j=i+1;j<nums.size();j++)
		{
			if(nums[i][j]==2)
			{
				Unite(i,j);
				deg[i]++,deg[j]++;
			}
		}
	}
	for(int i=0;i<nums.size();i++)
	{
		if(deg[i]>2)
		{
			return 0;
		}
	}
	for(int i=0;i<nums.size();i++)
	{
		for(int j=i+1;j<nums.size();j++)
		{
			if(Get(i)==Get(j))
			{
				ans[i][j]=1,ans[j][i]=1;
			}
		}
	}
	build(ans);
	return 1;
}

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