Submission #440279

#	Time	Username	Problem	Language	Result	Execution time	Memory
440279		MohamedAliSaidane	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	285 ms	31856 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
#define pb push_back
#define popb pop_back
#define ff first
#define ss second

vi par;
vi rnk;
int findset(int i)
{
    if(par[i] == i)
        return i;
    return findset(par[i]) ;
}
void unite(int i, int j)
{
    if(findset(i) == findset(j))
        return;
    int x = findset(i);
    int y = findset(j);
    if(rnk[x] < rnk[y])
        swap(x,y);
    par[y] = x;
    if(rnk[x] == rnk[y])
        rnk[x] ++;
    return ;
}
int construct(vector<vi> p)
 {
	int n = p.size();
	vector<vi> b;
	int maxt = 0;
	map<int,vi> m;
	for (int i = 0; i < n; i++)
    {
		vi row;
		for(int j = 0; j <n; j ++)
        {
            par.pb(j);
            rnk.pb(0);
            row.pb(0);
        }
		b.pb(row);
	}
	for(int i = 0; i <n; i ++)
	{
	    for(int j = 0; j < n; j ++)
        {
            if(i == j)
            {
                continue;
            }
            if(p[i][j] > 0)
            {
                maxt = max(p[i][j],maxt);
                unite(i,j);
            }
        }
	}
	for(int i = 0; i <n; i ++)
    {
        for(int j = 0; j < n; j ++)
        {
            if(i == j)
                continue;
            if((p[i][j] == 0 && findset(i) == findset(j)) || p[i][j] == 3)
                return 0;
        }
    }
    if(maxt == 1)
    {
        for(int i = 0; i <n; i ++)
        {
            if(i != par[i])
            {
                b[i][par[i]] = 1;
                b[par[i]][i] = 1;
            }
        }
    }
    else if (maxt == 2)
    {
        for(int i = 0; i <n ; i++)
        {
            m[findset(i)].pb(i);
        }
        for(auto e: m )
        {
            if(e.ss.size() == 2)
                return 0;
            for(int j = 0; j < e.ss.size() - 1; j ++)
            {
                b[e.ss[j]][e.ss[j+1]] = 1;
                b[e.ss[j+1]][e.ss[j]] = 1;
            }
            if(e.ss.size() != 1)
            {
                b[e.ss[0]][e.ss[e.ss.size()-1]] = 1;
                b[e.ss.size()-1][e.ss[0]] = 1;
            }
        }
    }
    build(b);
	return 1;
}
/*
6
1 1 1 0 0 0
1 1 1 0 0 0
1 1 1 0 0 0
0 0 0 1 1 1
0 0 0 1 1 1
0 0 0 1 1 1
*/

Compilation message (stderr)

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

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