Submission #306744

#	Time	Username	Problem	Language	Result	Execution time	Memory
306744		Ruxandra985	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	259 ms	22264 KiB

supertrees

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

using namespace std;

int tt[DIMN] , c[DIMN] , f[DIMN];
vector <int> x , cycle;


int root (int x){

    while (tt[x] > 0)
        x = tt[x];
    return x;

}


int construct(vector<vector<int>> p) {
	int n = p.size() , i , ri , rj , j , caz , r;
	vector<vector<int>> answer;
	for (i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}

	for (i = 0 ; i < n ; i++)
        tt[i] = -1;


	for (i = 0 ; i < n ; i++){
        f[i] = 0;
        c[i] = 0;
        for (j = 0 ; j < n ; j++){

            if (p[i][j] == 3)
                return 0; /// ce teapa monumentala

            if (p[i][j] && i != j){
                c[i] = (c[i] | p[i][j]);

                /// i si j in aceeasi componenta conexa

                ri = root(i);
                rj = root(j);

                if (ri != rj){

                    if (tt[ri] < tt[rj]){
                        tt[ri] += tt[rj];
                        tt[rj] = ri;
                    }
                    else {
                        tt[rj] += tt[ri];
                        tt[ri] = rj;
                    }

                }


            }


        }
	}


	for (i = 0 ; i < n ; i++){
        for (j = 0 ; j < n ; j++){

            if (!p[i][j]){

                /// i si j in aceeasi componenta conexa

                ri = root(i);
                rj = root(j);

                if (ri == rj) /// sunt in aceeasi cc si n ar trb sa fie
                    return 0;
            }
        }
	}

	for (r = 0 ; r < n ; r++){

        if (tt[r] < 0){

            x.clear();

            for (i = 0 ; i < n ; i++){
                if (root(i) == r)
                    x.push_back(i);
            }

            /// x = componenta conexa de acum

            caz = 0;
            for (i = 0 ; i < x.size() ; i++){
                caz = (caz | c[x[i]]);
            }

            if (caz == 0)
                continue;
            else if (caz == 1){ /// lant

                if (x.size() < 2)
                    return 0;
                for (i = 0 ; i < x.size() - 1 ; i++){
                    answer[x[i]][x[i + 1]] = answer[x[i + 1]][x[i]] = 1;
                }

            }
            else if (caz == 2){ /// un ciclu simplu

                if (x.size() < 3)
                    return 0;

                for (i = 0 ; i < x.size() - 1 ; i++){
                    answer[x[i]][x[i + 1]] = answer[x[i + 1]][x[i]] = 1;
                }

                answer[x[0]][x.back()] = answer[x.back()][x[0]] = 1;

            }
            else { /// cazul cand sunt si 1 si 2

                cycle.clear();
                int ok = 0;
                for (i = 0 ; i < x.size() ; i++){
                    if (c[x[i]] == 2){
                        cycle.push_back(x[i]);
                        f[x[i]] = 1;
                    }
                    else if (c[x[i]] == 1){
                        return 0;
                    }
                }

                for (i = 0 ; i < x.size() ; i++){
                    if (c[x[i]] == 3){
                        for (j = 0 ; j < n ; j++){
                            if (j != x[i]){

                                if (p[x[i]][j] == 1 && f[j] == 1)
                                    break;

                            }
                        }
                        if (j == n){
                            cycle.push_back(x[i]);
                            f[x[i]] = 1;

                            for (j = 0 ; j < n ; j++){
                                if (j != x[i]){

                                    if (p[x[i]][j] == 2 && f[j] == 0){
                                        cycle.push_back(j);
                                        f[j] = 1;
                                    }

                                }
                            }

                        }
                    }
                }


                if (cycle.size() < 3){
                    return 0;
                }

                for (i = 0 ; i < x.size() ; i++){
                    if (c[x[i]] == 3){
                        for (j = 0 ; j < n ; j++){
                            if (p[x[i]][j] == 1 && x[i] != j)
                                answer[x[i]][j] = answer[j][x[i]] = 1;
                        }
                    }
                }


                for (i = 0 ; i < cycle.size() - 1 ; i++){
                    answer[cycle[i]][cycle[i + 1]] = answer[cycle[i + 1]][cycle[i]] = 1;
                }

                answer[cycle[0]][cycle.back()] = answer[cycle.back()][cycle[0]] = 1;


            }


        }


	}

	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:100:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for (i = 0 ; i < x.size() ; i++){
      |                          ~~^~~~~~~~~~
supertrees.cpp:110:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |                 for (i = 0 ; i < x.size() - 1 ; i++){
      |                              ~~^~~~~~~~~~~~~~
supertrees.cpp:120:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |                 for (i = 0 ; i < x.size() - 1 ; i++){
      |                              ~~^~~~~~~~~~~~~~
supertrees.cpp:131:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |                 for (i = 0 ; i < x.size() ; i++){
      |                              ~~^~~~~~~~~~
supertrees.cpp:141:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |                 for (i = 0 ; i < x.size() ; i++){
      |                              ~~^~~~~~~~~~
supertrees.cpp:175:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |                 for (i = 0 ; i < x.size() ; i++){
      |                              ~~^~~~~~~~~~
supertrees.cpp:185:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |                 for (i = 0 ; i < cycle.size() - 1 ; i++){
      |                              ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:130:21: warning: unused variable 'ok' [-Wunused-variable]
  130 |                 int ok = 0;
      |                     ^~

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