Submission #1118059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118059		I_FloPPed21	Connecting Supertrees (IOI20_supertrees)	C++14	46 / 100	153 ms	28120 KiB

supertrees

#include "supertrees.h"
#include <iostream>
#include <vector>

using namespace std;
const int N=1001;
vector<vector<int>>b;
int n,componente[N],cnt,root[N],modes[N][N];
bool viz[N];
int tine_root[N];
void fa_dfs(int i)
{
    viz[i]=true;
    componente[i]=cnt;
    for(int j=0; j<n; j++)
    {
        if(viz[j]==true)
            continue;
        if(modes[i][j]==1)
        {
            b[i][j]=1;
            b[j][i]=1;
            tine_root[j]=tine_root[i];
            fa_dfs(j);
        }
    }
}

bool e_root[N];
vector<int>adj[N];
bool viz2[N];
bool nah=false;
int comp=0,where[N];
void fa_dfs2(int nod)
{
    adj[comp].push_back(nod);
    viz2[nod]=true;
    where[nod]=comp;
    for(int j=0; j<n; j++)
    {
        if(viz2[j]==true)
            continue;
        if(e_root[j]==false)
            continue;
        if(modes[nod][j]==2)
        {
            b[nod][j]=1;
            b[j][nod]=1;
            fa_dfs2(j);
        }
    }
}
int construct(vector<vector<int>>p)
{
    n=p.size();
    b.resize(n);
    for(int i=0; i<n; i++)
        b[i].resize(n);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
        {
            modes[i][j]=p[i][j];
            if(modes[i][j]==3)
            {
                return 0;
            }
        }
    for(int i=0; i<n; i++)
    {
        if(viz[i]==false)
        {
            cnt++;
            viz[i]=true;
            e_root[i]=true;
            tine_root[i]=i;
            componente[i]=cnt;
            fa_dfs(i);
        }
    }

    for(int i=0; i<n; i++)
    {
        if(e_root[i]&&viz2[i]==false)
        {
            comp++;
            fa_dfs2(i);
        }
    }
    for(int i=1; i<=comp; i++)
    {
        if(adj[i].size()==2)
            nah=true;

        if(adj[i].size()>2)
        {
            b[adj[i].back()][adj[i][0]]=1;
            b[adj[i][0]][adj[i].back()]=1;
        }
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(modes[i][j]!=modes[j][i])
            {
                nah=true;
            }

            if(i==j&&modes[i][j]!=0)
            {
                nah=false;
            }
            if(i==j)
                continue;

            if(modes[i][j]==0&&(componente[i]==componente[j]||where[tine_root[i]]==where[tine_root[j]]))
                nah=true;
            if(modes[i][j]==1&&componente[i]!=componente[j])
                nah=true;

            if(modes[i][j]==1&&where[tine_root[i]]==where[tine_root[j]])
                nah=true;

            if(modes[i][j]==2&&componente[i]==componente[j])
                nah=true;
            if(modes[i][j]==2&&where[tine_root[i]]!=where[tine_root[j]])
                nah=true;
        }
    }
    if(nah==true)
        return 0;
    build(b);
    return 1;
}

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