Submission #635953

#	Time	Username	Problem	Language	Result	Execution time	Memory
635953		FETT	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	177 ms	24056 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

int nn;
vector<vector<int>> answer;
int head[1001];
vector<int> visit[1001];


//void c_head()
//{
//    cout<<"head"<<endl;
//    for(int i=0;i<nn;++i)
//    {
//        cout<<head[i]<<" ";
//    }cout<<endl;
//}

int f_head(int &x)
{
    if(head[x]==x)
    {
        return x;
    }
    return head[x]=f_head(x);
}

int construct(vector<vector<int>> p) {
	nn = p.size();

	for (int i = 0; i < nn; i++) {
        head[i]=i;
		vector<int> row;
		row.resize(nn);
		answer.push_back(row);
	}

	for(int i=0;i<nn;++i)
    {
        if(p[i][0]==-1)continue;
        for(int j=0;j<nn;++j)
        {
            if(p[i][j]==-1)continue;
            if(p[i][j]!=p[j][i])return 0;
            if(p[i][j]==3)return 0;
            if(p[i][j]==1)
            {
                head[j]=i;
                for(int k=0;k<visit[i].size();++k)
                {
                    if(p[j][visit[i][k]]!=1)return 0;
                }
                visit[i].push_back(j);
                if(i!=j)
                {
                    p[j][0]=-1;
                    answer[i][j]=1;
                    answer[j][i]=1;
                }
            }
        }
    }
//    c_head();
//    cout<<"P"<<endl;
//    for(int i=0;i<nn;++i)
//    {
//        for(int j=0;j<nn;++j)
//        {
//            cout<<p[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    for(int i=0;i<nn;++i)
    {
        bool flag=0;
        if(p[i][0]==-1)continue;
        for(int j=0;j<nn;++j)
        {
            if(p[i][j]==2)
            {
                flag=1;
                p[j][0]=-1;
                answer[head[i]][head[j]]=1;
                answer[head[j]][head[i]]=1;
                head[i]=j;
            }
        }
        if(flag==1)
        {
            answer[i][head[i]]=1;
            answer[head[i]][i]=1;
        }

    }

//    c_head();

	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:51:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                 for(int k=0;k<visit[i].size();++k)
      |                             ~^~~~~~~~~~~~~~~~

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