Submission #303348

#	Time	Username	Problem	Language	Result	Execution time	Memory
303348		baluteshih	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	278 ms	22396 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(),v.end()
#define SZ(a) ((int)a.size())
#define pb push_back

int boss[1005];
vector<int> cpn[1005],tree[1005];
vector<vector<int>> answer;

int finds(int x)
{
    if(x==boss[x]) return boss[x];
    return boss[x]=finds(boss[x]);
}

void Union(int x,int y)
{
    x=finds(x),y=finds(y);
    boss[y]=x;
}

void add_edge(int a,int b)
{
    answer[a][b]=answer[b][a]=1;
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	answer=vector<vector<int>>(n,vector<int>(n,0));
    vector<int> head;
    for(int i=0;i<n;++i)
        boss[i]=i;
    for(int i=0;i<n;++i)    
        for(int j=i+1;j<n;++j)
            if(p[i][j]>0)
                Union(i,j);
    for(int i=0;i<n;++i)
        for(int j=i+1;j<n;++j)
            if(finds(i)==finds(j)&&p[i][j]==0)
                return 0;
            else if(finds(i)!=finds(j)&&p[i][j]>0)
                return 0;
    for(int i=0;i<n;++i)
        cpn[finds(i)].pb(i);
    for(int i=0;i<n;++i)
        if(!cpn[i].empty())
        {
            vector<int> head;
            for(int j:cpn[i])
                boss[j]=j;
            for(int j=0;j<SZ(cpn[i]);++j)
                for(int k=j+1;k<SZ(cpn[i]);++k)
                    if(p[cpn[i][j]][cpn[i][k]]==1)
                        Union(cpn[i][j],cpn[i][k]);
            for(int j=0;j<SZ(cpn[i]);++j)
                for(int k=j+1;k<SZ(cpn[i]);++k)
                    if(finds(cpn[i][j])==finds(cpn[i][k])&&p[cpn[i][j]][cpn[i][k]]!=1)
                        return 0;
                    else if(finds(cpn[i][j])!=finds(cpn[i][k])&&p[cpn[i][j]][cpn[i][k]]!=2)
                        return 0;
            for(int j:cpn[i])
                tree[finds(j)].pb(j);
            for(int j:cpn[i])
                if(!tree[j].empty())
                {
                    head.pb(tree[j][0]);
                    for(int k=1;k<SZ(tree[j]);++k)
                        add_edge(tree[j][k-1],tree[j][k]);
                }
            if(SZ(head)==2)
                return 0;
            for(int i=1;i<SZ(head);++i)
                add_edge(head[i-1],head[i]);
            if(SZ(head)>1)
                add_edge(head[0],head.back());
        }
    build(answer);
	return 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