Submission #306757

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

supertrees

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

using namespace std;

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


int root (int x){

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

}

int roott (int x){

    while (t[x] > 0)
        x = t[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

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


                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++){
                    for (j = 0 ; j < x.size() ; j++){

                        //if (r == 24)
                        //printf ("a");

                        if (i != j && p[x[i]][x[j]] == 1){


                            ri = roott(x[i]);
                            rj = roott(x[j]);

                            if (ri != rj){

                                answer[ri][rj] = answer[ri][rj] = 1;

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

                            }

                        }

                    }
                }

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

                        ri = roott(x[i]);

                        if (!f[ri]){
                            f[ri] = 1;
                            cycle.push_back(ri);
                        }
                    }
                }


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


                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;


            }


        }


	}

	//printf ("%d\n\n",answer[0][228]);

	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:108:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             for (i = 0 ; i < x.size() ; i++){
      |                          ~~^~~~~~~~~~
supertrees.cpp:118:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |                 for (i = 0 ; i < x.size() - 1 ; i++){
      |                              ~~^~~~~~~~~~~~~~
supertrees.cpp:128:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |                 for (i = 0 ; i < x.size() - 1 ; i++){
      |                              ~~^~~~~~~~~~~~~~
supertrees.cpp:143:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |                 for (i = 0 ; i < x.size() ; i++){
      |                              ~~^~~~~~~~~~
supertrees.cpp:153:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |                 for (i = 0 ; i < x.size() ; i++){
      |                              ~~^~~~~~~~~~
supertrees.cpp:154:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |                     for (j = 0 ; j < x.size() ; j++){
      |                                  ~~^~~~~~~~~~
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 < x.size() ; i++){
      |                              ~~^~~~~~~~~~
supertrees.cpp:203:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |                 for (i = 0 ; i < cycle.size() - 1 ; i++){
      |                              ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:142:21: warning: unused variable 'ok' [-Wunused-variable]
  142 |                 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