Submission #678215

#	Time	Username	Problem	Language	Result	Execution time	Memory
678215		yellowtoad	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	298 ms	22396 KiB

supertrees

#include <iostream>
#include <vector>
using namespace std;

void build(std::vector<std::vector<int>> b);

int construct(std::vector<std::vector<int>> a) {
	int n = a.size(), cnt = 0, num[1010], cntt[1010], maxx;
    pair<int,int> id[1010];
	std::vector<std::vector<int>> edge;
    vector<vector<vector<int>>> grp;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (a[i][j] == 3) return 0;
    for (int i = 0; i < n; i++) if (a[i][i] != 1) return 0;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (a[i][j] != a[j][i]) return 0;
    for (int i = 0; i < n; i++) id[i] = {-1,-1};
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) if (a[i][j]) if (id[i].first != id[j].first) return 0;
        if (id[i].first == -1) {
            id[i].first = cnt++;
            maxx = 0;
            for (int j = i+1; j < n; j++) if (a[i][j]) id[j].first = id[i].first;
            for (int j = i+1; j < n; j++) maxx = max(maxx,a[i][j]);
            num[cnt-1] = maxx;
        }
        for (int j = 0; j < n; j++) if (id[i].first == id[j].first) if (!a[i][j]) return 0;
        if (id[i].second != -1) {
            for (int j = 0; j < n; j++) {
                if (id[j].first == id[i].first) {
                    if (id[j].second == id[i].second) {
                        if (a[i][j] != 1) return 0;
                    } else if (a[i][j] != num[id[i].first]) return 0;
                }
            }
        } else {
            id[i].second = cntt[id[i].first]++;
            for (int j = 0; j < n; j++) {
                if (id[j].first == id[i].first) {
                    if (a[i][j] == 1) id[j].second = id[i].second;
                    if (id[j].second != id[i].second) {
                        if (a[i][j] != num[id[i].first]) return 0;
                    }
                }
            }
        }
    }
    for (int i = 0; i < cnt; i++) {
        if (num[i] == 1) {
            if (cntt[i] != 1) return 0;
        } else if (num[i] >= 2) {
            if (cntt[i] <= num[i]) return 0;
        }
    }
    for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		edge.push_back(row);
	}
    for (int i = 0; i < cnt; i++) {
        std::vector<vector<int>> row;
		row.resize(cntt[i]);
		grp.push_back(row);
    }
    for (int i = 0; i < n; i++) grp[id[i].first][id[i].second].push_back(i);
    for (int i = 0; i < cnt; i++) {
        for (int j = 0; j < cntt[i]; j++) {
            for (int k = 1; k < grp[i][j].size(); k++) {
                edge[grp[i][j][k-1]][grp[i][j][k]] = 1;
                edge[grp[i][j][k]][grp[i][j][k-1]] = 1;
            }
        }
    }
    for (int i = 0; i < cnt; i++) {
        if (num[i] >= 2) {
            for (int j = 1; j < cntt[i]; j++) {
                edge[grp[i][j][0]][grp[i][j-1][0]] = 1;
                edge[grp[i][j-1][0]][grp[i][j][0]] = 1;
            }
            edge[grp[i][cntt[i]-1][0]][grp[i][0][0]] = 1;
            edge[grp[i][0][0]][grp[i][cntt[i]-1][0]] = 1;
        }
    }
	build(edge);
	return 1;
}

#ifdef EVEL
namespace var{
	std::vector<std::vector<int>> b;
};

void build(std::vector<std::vector<int>> b) {
    var::b = b;
}

int main() {
	int n;
    scanf("%d", &n);
    std::vector<std::vector<int>> p;
    
    p.resize(n);
    for (int i = 0; i < n; i++) {
        p[i].resize(n);
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &p[i][j]);
        }
    }

    int possible = construct(p);

    printf("%d\n", possible);
    if (possible == 1) {
        for (int i = 0; i < var::b.size(); i++) {
            for (int j = 0; j < var::b[i].size(); j++) {
                if (j) {
                    printf(" ");
                }
                printf("%d", var::b[i][j]);
            }
            printf("\n");
        }
    }
}
#endif

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:66:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for (int k = 1; k < grp[i][j].size(); k++) {
      |                             ~~^~~~~~~~~~~~~~~~~~

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