Submission #479809

#	Time	Username	Problem	Language	Result	Execution time	Memory
479809		stefantaga	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	280 ms	32196 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>

using namespace std;
int viz[1005],q,componentus[1005],n;
vector <int> comp[1005];
vector <vector<int>> p;
void dfs(int x)
{
    viz[x]=1;
    comp[q].push_back(x);
    componentus[x]=q;
    for (int j=0;j<n;j++)
    {
        if (viz[j]==0&&p[j][x]!=0)
        {
            dfs(j);
        }
    }
}
int matrice[1005][1005],rang[1005],tata[1005],fr[1005];
int parinte (int x)
{
    if (tata[x]!=x)
    {
        return parinte(tata[x]);
    }
    return x;
}
void uneste(int x,int y)
{
    x=parinte(x);
    y=parinte(y);
    if (x==y)
    {
        return ;
    }
    if (rang[x]<rang[y])
    {
        tata[x]=y;
    }
    else
    if (rang[x]>rang[y])
    {
        tata[y]=x;
    }
    else
    {
        tata[x]=y;
        rang[y]++;
    }
}
void dfs2(int x)
{
    viz[x]=1;
    for (int j=0;j<n;j++)
    {
        if (viz[j]==0&&p[j][x]==1)
        {
            matrice[x][j]=matrice[j][x]=1;
            dfs2(j);
        }
    }
}
vector <int> comp2[1005];
int construct(std::vector<std::vector<int>> alo) {
	n = alo.size();
	int i,j,k;
	p=alo;
	q=0;
	for (i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
        {
            if (p[i][j]==3)
            {
                return 0;
            }
        }
    }
    for (i=0;i<n;i++)
    {
        if (viz[i]==0)
        {
            q++;
            dfs(i);
        }
    }
    for (i=1;i<=q;i++)
    {
        for (j=0;j<comp[i].size();j++)
        {
            for (k=0;k<comp[i].size();k++)
            {
                int nod1=comp[i][j];
                int nod2=comp[i][k];
                if (p[nod1][nod2]==0)
                {
                    return 0;
                }
            }
        }
    }
    for (i=0;i<n;i++)
    {
        tata[i]=i;
        rang[i]=1;
    }
    for (i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
        {
            if (p[i][j]==1)
            {
                uneste(i,j);
            }
        }
    }
    for (i=0;i<n;i++)
    {
        fr[parinte(i)]=1;
        comp2[parinte(i)].push_back(i);
    }
    for (i=0;i<n;i++)
    {
        if (fr[i]==1)
        {
            for (int j=0;j<comp2[i].size();j++)
            {
                for (int t=0;t<comp2[i].size();t++)
                {
                    int nod1=comp2[i][j];
                    int nod2=comp2[i][t];
                    if (p[nod1][nod2]!=1)
                    {
                        return 0;
                    }
                }
            }
        }
    }
    for (i=0;i<n;i++)
    {
        viz[i]=0;
    }
    for (i=1;i<=q;i++)
    {
        vector <int> ceau;
        for (j=0;j<comp[i].size();j++)
        {
            int nod1=comp[i][j];
            if (viz[nod1]==0)
            {
                ceau.push_back(nod1);
                dfs2(nod1);
            }
        }
        if (ceau.size()==2)
        {
            return 0;
        }
        if (ceau.size()==1)
        {
            continue;
        }
        for (j=0;j<ceau.size()-1;j++)
        {
            matrice[ceau[j]][ceau[j+1]]=matrice[ceau[j+1]][ceau[j]]=1;
        }
        matrice[ceau[0]][ceau[ceau.size()-1]]=matrice[ceau[ceau.size()-1]][ceau[0]]=1;
    }
    vector <vector<int>> sol;
    sol.resize(n);
    for (i=0;i<n;i++)
    {
        sol[i].resize(n);
    }
    for (i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
        {
            sol[i][j]=matrice[i][j];
        }
    }
    build(sol);
	return 1;
}


#ifdef HOME
static int n2;
static std::vector<std::vector<int>> p3;
static std::vector<std::vector<int>> b;
static bool called = false;

static void check(bool cond, std::string message) {
    if (!cond) {
        printf("%s\n", message.c_str());
        fclose(stdout);
        exit(0);
    }
}

void build(std::vector<std::vector<int>> _b) {
    check(!called, "build is called more than once");
    called = true;
    check((int)_b.size() == n2, "Invalid number of rows in b");
    for (int i = 0; i < n2; i++) {
        check((int)_b[i].size() == n2, "Invalid number of columns in b");
    }
    b = _b;
}

int main() {
    assert(scanf("%d", &n2) == 1);

    p3.resize(n2);
    for (int i = 0; i < n2; i++) {
        p3[i].resize(n2);
    }

    for (int i = 0; i < n2; i++) {
        for (int j = 0; j < n2; j++) {
            assert(scanf("%d", &p3[i][j]) == 1);
        }
    }
    fclose(stdin);

    int possible = construct(p3);

    check(possible == 0 || possible == 1, "Invalid return value of construct");
    if (possible == 1) {
        check(called, "construct returned 1 without calling build");
    } else {
        check(!called, "construct called build but returned 0");
    }

    printf("%d\n", possible);
    if (possible == 1) {
        for (int i = 0; i < n2; i++) {
            for (int j = 0; j < n2; j++) {
                if (j) {
                    printf(" ");
                }
                printf("%d", b[i][j]);
            }
            printf("\n");
        }
    }
    fclose(stdout);
}

#endif // HOME

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for (j=0;j<comp[i].size();j++)
      |                  ~^~~~~~~~~~~~~~~
supertrees.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             for (k=0;k<comp[i].size();k++)
      |                      ~^~~~~~~~~~~~~~~
supertrees.cpp:133:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |             for (int j=0;j<comp2[i].size();j++)
      |                          ~^~~~~~~~~~~~~~~~
supertrees.cpp:135:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |                 for (int t=0;t<comp2[i].size();t++)
      |                              ~^~~~~~~~~~~~~~~~
supertrees.cpp:154:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |         for (j=0;j<comp[i].size();j++)
      |                  ~^~~~~~~~~~~~~~~
supertrees.cpp:171:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |         for (j=0;j<ceau.size()-1;j++)
      |                  ~^~~~~~~~~~~~~~

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