Submission #306762

#	Time	Username	Problem	Language	Result	Execution time	Memory
306762		Ruxandra985	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	260 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[rj][ri] = 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: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4