Submission #304810

#	Time	Username	Problem	Language	Result	Execution time	Memory
304810		azberjibiou	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	262 ms	26276 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
const int mxN=1010;
using namespace std;
int N;
int Col1[mxN], Col2[mxN], idx1=1, idx2=1;
vector <int> col2s[mxN], col1s[mxN];
int tmp[mxN], idxt;
vector <int> P[mxN];
void dfs1(int num)
{
    for(int i=0;i<N;i++)
    {
        if(P[num][i]!=0 && Col1[i]==0)
        {
            Col1[i]=Col1[num];
            dfs1(i);
        }
    }
}
void dfs2(int col, int num)
{
    col2s[col].push_back(num);
    for(int i=0;i<N;i++)
    {
        if(P[num][i]==1 && Col2[i]==0)
        {
            Col2[i]=Col2[num];
            dfs2(col, i);
        }
    }
}
int construct(vector<vector<int>> p) {
	N = p.size();
	vector<vector<int>> ans;
	for (int i = 0; i < N; i++) {
		vector<int> row;
		row.resize(N);
		ans.push_back(row);
	}
	for(int i=0;i<N;i++)
    {
        P[i].resize(N);
        for(int j=0;j<N;j++)
        {
            P[i][j]=p[i][j];
        }
    }
	for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            if(P[i][j]==3)  return 0;
        }
    }
    for(int i=0;i<N;i++)
    {
        if(Col1[i]==0)
        {
            Col1[i]=idx1++;
            dfs1(i);
        }
    }
    for(int i=1;i<idx1;i++)
    {
        idxt=0;
        for(int j=0;j<N;j++)
        {
            if(Col1[j]==i)  tmp[idxt++]=j;
        }
        for(int j=0;j<idxt;j++)
        {
            for(int k=j+1;k<idxt;k++)
            {
                if(P[tmp[j]][tmp[k]]==0)  return 0;
            }
        }
    }
    for(int i=1;i<idx1;i++)
    {
        for(int j=0;j<N;j++)
        {
            if(Col1[j]==i && Col2[j]==0)
            {
                col1s[i].push_back(idx2);
                Col2[j]=idx2;
                dfs2(idx2, j);
                idx2++;
            }
        }
    }
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            if(Col2[i]==Col2[j])
            {
                if(P[i][j]!=1)  return 0;
            }
            else if(Col1[i]==Col1[j])
            {
                if(P[i][j]!=2)  return 0;
            }
            else
            {
                if(P[i][j]!=0)  return 0;
            }
        }
    }
    for(int i=1;i<idx2;i++)
    {
        if(col2s[i].empty())    continue;
        for(int j=0;j<col2s[i].size()-1;j++)
        {
            int now=col2s[i][j], nxt=col2s[i][j+1];
            ans[now][nxt]=1;
            ans[nxt][now]=1;
        }
    }
    for(int i=1;i<idx1;i++)
    {
        if(col1s[i].empty())    continue;
        if(col1s[i].size()==1)  continue;
        if(col1s[i].size()==2)  return 0;
        col1s[i].push_back(col1s[i][0]);
        for(int j=0;j<col1s[i].size()-1;j++)
        {
            int now=col2s[col1s[i][j]][0], nxt=col2s[col1s[i][j+1]][0];
            ans[now][nxt]=1;
            ans[nxt][now]=1;
        }
    }
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(int j=0;j<col2s[i].size()-1;j++)
      |                     ~^~~~~~~~~~~~~~~~~~
supertrees.cpp:131:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for(int j=0;j<col1s[i].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