Submission #366890

#	Time	Username	Problem	Language	Result	Execution time	Memory
366890		rumen_m	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1097 ms	35052 KiB

supertrees

#include "supertrees.h"
#include <vector>
using namespace std;
const int maxn = 1005;
vector <int> g[maxn];
vector <int> ones[maxn];
int id[maxn], ids = 0;
bool vis[maxn];
vector <int> groups[maxn];
int ans[maxn][maxn];
void dfs(int v)
{
    id[v]=ids;
    int i;
    for(i=0;i<g[v].size();i++)
    {
        if(id[g[v][i]]==0)dfs(g[v][i]);
    }
}
void solve(int v)
{
    vis[v] = 1;
    int i;
    for(i=0;i<ones[v].size();i++)
    {
        if(!vis[ones[v][i]])
        {
            ans[v][ones[v][i]] = 1;
            solve(ones[v][i]);
        }
    }
}
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	int i,j,t;
	for(i=0;i<n;i++)
        for(j=0;j<n;j++)
    {
        if(i==j)continue;
        if(p[i][j]==3)return 0;
        if(p[i][j]>0)
        {
            for(t=0;t<n;t++)
            {
                 if((p[i][t]>0)^(p[j][t]>0)==1)return 0;
                 if(p[i][j]==1)
                    if(p[i][t]==1^p[j][t]==1)return 0;
            }

        }
        if(p[i][j]!=0)
        {
            g[i].push_back(j);
            g[j].push_back(i);
        }
        if(p[i][j]==1)
        {
            ones[i].push_back(j);
            ones[j].push_back(i);
        }
    }
    for(i=0;i<n;i++)
    {
        if(id[i]==0){ids++;dfs(i);}
    }
    for(i=0;i<n;i++)
    {
        if(!vis[i])
        {
            groups[id[i]].push_back(i);
            solve(i);
        }
    }
    for(i=1;i<=ids;i++)
    {
        if(groups[i].size()==2)return 0;
        if(groups[i].size()<=2)continue;
        ans[groups[i][0]][groups[i][groups[i].size()-1]] = 1;
        for(j=1;j<groups[i].size();j++)
        {
            ans[groups[i][j-1]][groups[i][j]] = 1;
        }
    }
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		for(j=0;j<n;j++)
            row[j] = ans[i][j]||ans[j][i];
		answer.push_back(row);
	}
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void dfs(int)':
supertrees.cpp:15:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(i=0;i<g[v].size();i++)
      |             ~^~~~~~~~~~~~
supertrees.cpp: In function 'void solve(int)':
supertrees.cpp:24:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(i=0;i<ones[v].size();i++)
      |             ~^~~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:45:44: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   45 |                  if((p[i][t]>0)^(p[j][t]>0)==1)return 0;
      |                                 ~~~~~~~~~~~^~~
supertrees.cpp:47:31: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   47 |                     if(p[i][t]==1^p[j][t]==1)return 0;
supertrees.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(j=1;j<groups[i].size();j++)
      |                 ~^~~~~~~~~~~~~~~~~

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