Submission #1193529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193529		simona1230	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	160 ms	35708 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

int a[1024][1024];
int l[1024],s[1024];

int fl(int i)
{
    if(i==l[i])return i;
    return l[i]=fl(l[i]);
}

void unite(int i,int j)
{
    int li=fl(i);
    int lj=fl(j);
    if(li!=lj)
    {
        l[li]=lj;
        s[lj]+=s[li];
    }
}

vector<int> v[200001],v2[200001];
vector<vector<int> > ans;

int construct(std::vector<std::vector<int>> p)
{
    int n=p.size();

    for(int i=0; i<n; i++)
    {
        l[i]=i;
        s[i]=1;
    }

    for(int i=0; i<n; i++)
    {
        ans.push_back({});
        for(int j=0; j<n; j++)
        {
            ans[i].push_back(0);
            a[i][j]=p[i][j];
            
            if(a[i][j]==3)return 0;
            if(a[i][j]==1)
            {
                //cout<<"+ "<<i<<" "<<j<<endl;
                unite(i,j);
            }
        }
    }

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(a[i][j]!=1)
            {
                //cout<<i<<" "<<j<<endl;
                int li=fl(i);
                int lj=fl(j);
                if(li==lj)return 0;
            }
        }
    }

    for(int i=0; i<n; i++)
    {
        int li=fl(i);
        v[li].push_back(i);
    }

    for(int i=0; i<n; i++)
        l[i]=i,s[i]=1;

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(v[i].size()==0||v[j].size()==0)continue;
            if(a[i][j]==2)
            {
                //cout<<i<<" + "<<j<<endl;
                unite(i,j);
            }
        }
    }

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(v[i].size()==0||v[j].size()==0)continue;
            for(int ii=0;ii<v[i].size();ii++)
            {
                for(int jj=0;jj<v[j].size();jj++)
                {
                    int x=v[i][ii];
                    int y=v[j][jj];
                    int lx=fl(i);
                    int ly=fl(j);
                    if(a[x][y]==0&&lx==ly||a[x][y]==2&&lx!=ly)return 0;
                }
            }
        }
    }

    for(int i=0; i<n; i++)
    {
        if(v[i].size()==0)continue;
        int li=fl(i);
        v2[li].push_back(i);
    }

    for(int i=0; i<n; i++)
    {
        if(v[i].size()<=1)continue;
        for(int j=0; j<v[i].size()-1; j++)
        {
            ans[v[i][j]][v[i][j+1]]=ans[v[i][j+1]][v[i][j]]=1;
        }
    }

    for(int i=0;i<n;i++)
    {
        //cout<<i<<" : "<<v2[i].size()<<endl;
        if(v2[i].size()==2)return 0;
        for(int j=0; j<(int)v2[i].size()-1; j++)
        {
            //cout<<"in"<<endl;
            //cout<<v2[i][j]<<" "<<v2[i].size()<<endl;
            ans[v2[i][j]][v2[i][j+1]]=ans[v2[i][j+1]][v2[i][j]]=1;
        }
        if(v2[i].size()>2)ans[v2[i][0]][v2[i][v2[i].size()-1]]=ans[v2[i][v2[i].size()-1]][v2[i][0]]=1;
    }

    build(ans);

    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