Submission #519125

#	Time	Username	Problem	Language	Result	Execution time	Memory
519125		LucaIlie	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	194 ms	24300 KiB

supertrees

#include <iostream>
#include <vector>
#include "supertrees.h"
 
#define MAX_N 1000
 
using namespace std;
 
struct dsu {
    int n;
    int sef[MAX_N];
 
    void init( int x ) {
        int i;
 
        n = x;
        for ( i = 0; i < n; i++ )
            sef[i] = i;
    }
 
    int find( int x ) {
        if ( sef[x] != x )
            sef[x] = find( sef[x] );
        return sef[x];
    }
 
    void unionn( int x, int y ) {
        x = find( x );
        y = find( y );
        sef[y] = x;
    }
};
 
int construct( vector <vector <int>> p ) {
    int n, a, x, y, i, j;
    dsu forest;
    vector <int> f[MAX_N];
 
    n = p.size();
    vector <vector <int>> b( n );
    forest.init( n );
 
 
    for ( x = 0; x < n; x++ ) {
        for ( y = 0; y < n; y++ ) {
            if ( p[x][y] > 0 )
                forest.unionn( x, y );
        }
    }
 
    for ( x = 0; x < n; x++ )
        f[forest.find( x )].push_back( x );
 
    for ( i = 0; i < n; i++ ) {
        for ( j = 0; j < n; j++ )
            b[i].push_back( 0 );
    }
    for ( x = 0; x < n; x++ ) {
        if ( f[x].size() ) {
            a = p[f[x][0]][f[x][0]];
            for ( i = 0; i < f[x].size(); i++ ) {
                for ( j = 0; j < f[x].size(); j++ ) {
                    if ( a != p[f[x][i]][f[x][j]] )
                        return 0;
                }
            }
            for ( i = 0; i < f[x].size() - 1; i++ ) {
                b[f[x][i]][f[x][i + 1]] = 1;
                b[f[x][i + 1]][f[x][i]] = 1;
            }
            if ( f[x].size() < a )
                return 0;
            for ( i = 1; i < a; i++ ) {
                b[f[x][0]][f[x][i]] = 1;
                b[f[x][i]][f[x][0]] = 1;
            }
        }
    }
 
    build( b );
 
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:61:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             for ( i = 0; i < f[x].size(); i++ ) {
      |                          ~~^~~~~~~~~~~~~
supertrees.cpp:62:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                 for ( j = 0; j < f[x].size(); j++ ) {
      |                              ~~^~~~~~~~~~~~~
supertrees.cpp:67:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             for ( i = 0; i < f[x].size() - 1; i++ ) {
      |                          ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:71:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |             if ( f[x].size() < a )
      |                  ~~~~~~~~~~~~^~~

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