Submission #519915

#	Time	Username	Problem	Language	Result	Execution time	Memory
519915		LucaIlie	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	233 ms	24128 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, x, y, i, j, first, last, sef1, sef2, e2;
    dsu forest1, forest2;
    vector <int> f1[MAX_N], f2[MAX_N];

    n = p.size();
    vector <int> v;
    vector <vector <int>> b( n );
    forest1.init( n );
    forest2.init( n );


    for ( x = 0; x < n; x++ ) {
        for ( y = 0; y < n; y++ ) {
            if ( p[x][y] >= 1 )
                forest1.unionn( x, y );
            if ( p[x][y] == 1 )
                forest2.unionn( x, y );
        }
    }

    for ( x = 0; x < n; x++ ) {
        f1[forest1.find( x )].push_back( x );
        f2[forest2.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++ ) {
        v = f1[x];
        if ( v.size() > 1 ) {
            e2 = 0;
            for ( i = 0; i < v.size(); i++ ) {
                for ( j = i + 1; j < v.size(); j++ ) {
                    if ( p[v[i]][v[j]] == 0 )
                        return 0;
                    if ( p[v[i]][v[j]] == 2 )
                        e2 = 1;
                }
            }
            if ( e2 ) {
                if ( v.size() == 2 )
                    return 0;
                sef1 = sef2 = -1;
                for ( i = 0; i < v.size(); i++ ) {
                    if ( forest2.find( v[i] ) != v[i] && forest2.find( v[i] ) != sef1 && forest2.find( v[i] ) != sef2 ) {
                        if ( sef1 == -1 )
                            sef1 = forest2.find( v[i] );
                        else if ( sef2 == -1 )
                            sef2 = forest2.find( v[i] );
                        //else
                            //return 0;
                    }
                }
                first = -1;
                last = -1;
                for ( i = 0; i < v.size(); i++ ) {
                    if ( forest2.find( v[i] ) != v[i] ) {
                        b[v[i]][forest2.find( v[i] )] = 1;
                        b[forest2.find( v[i] )][v[i]] = 1;
                    } else {
                        if ( last != -1 ) {
                            b[last][v[i]] = 1;
                            b[v[i]][last] = 1;
                        }
                        if ( first == -1 )
                            first = v[i];
                        last = v[i];
                    }
                }
                if ( first != last ) {
                    b[first][last] = 1;
                    b[last][first] = 1;
                }
                for ( i = 0; i < v.size(); i++ ) {
                    for ( j = i + 1; j < v.size(); j++ ) {
                        if ( forest2.find( v[i] ) == forest2.find( v[j] ) ) {
                            if ( p[v[i]][v[j]] != 1 )
                                return 0;
                        } else {
                            if ( p[v[i]][v[j]] != 2 )
                                return 0;
                        }
                    }
                }
            } else {
                for ( i = 0; i < v.size() - 1; i++ ) {
                    b[v[i]][v[i + 1]] = 1;
                    b[v[i + 1]][v[i]] = 1;
                }
            }
        }
    }

    build( b );

    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:69:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for ( i = 0; i < v.size(); i++ ) {
      |                          ~~^~~~~~~~~~
supertrees.cpp:70:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                 for ( j = i + 1; j < v.size(); j++ ) {
      |                                  ~~^~~~~~~~~~
supertrees.cpp:81:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |                 for ( i = 0; i < v.size(); i++ ) {
      |                              ~~^~~~~~~~~~
supertrees.cpp:93:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                 for ( i = 0; i < v.size(); i++ ) {
      |                              ~~^~~~~~~~~~
supertrees.cpp:111:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |                 for ( i = 0; i < v.size(); i++ ) {
      |                              ~~^~~~~~~~~~
supertrees.cpp:112:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |                     for ( j = i + 1; j < v.size(); j++ ) {
      |                                      ~~^~~~~~~~~~
supertrees.cpp:123:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |                 for ( i = 0; i < v.size() - 1; i++ ) {
      |                              ~~^~~~~~~~~~~~~~

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