Submission #1066373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066373		allin27x	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	168 ms	24148 KiB

supertrees

#include <bits/stdc++.h>
using namespace std;


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

int solve(vector<vector<int>> &p, vector<int> &rel, vector<vector<int>> &b) {
    vector<vector<int>> cmp;
    vector<int> cp(p.size(), 0);
    for (int i: rel) {
        int c = -1;
        for (int j = 0; j < cmp.size(); j++) {
            for (int x: cmp[j]) {
                if (p[i][x] == 1) c = j;
            }
        }
        for (int j = 0; j < cmp.size(); j++) {
            for (int x: cmp[j]) {
                if ((p[i][x]==1)  ^ (j==c)) return 0;
            }
        }
        if (c==-1) cmp.push_back({i}), cp[i] = cmp.size()-1; else cmp[c].push_back(i),cp[i] = c;
    }
    for (int i: rel) for (int j: rel) {
        if (cp[i] == cp[j] && p[i][j] != 1) return 0;
        if (cp[i] != cp[j] && p[i][j] != 2) return 0;
    }
    for (auto cm: cmp) {
        for (int i=0; i<cm.size()-1; i++) {
            b[cm[i]][cm[i+1]] = 1;
            b[cm[i+1]][cm[i]] = 1;
        }
    }
    if (cmp.size() == 2) return 0;
    if (cmp.size() == 1) return 1;
    for (int j=0; j<cmp.size()-1; j++) {
        b[cmp[j][0]][cmp[j+1][0]] = 1;
        b[cmp[j+1][0]][cmp[j][0]] = 1;
    }
    b[cmp[0][0]][cmp.back()[0]] = 1;
    b[cmp.back()[0]][cmp[0][0]] = 1;
    return 1;
}

int construct(vector<vector<int>> p) {
    int n = p.size();
    for (int i = 0; i < n; i++) for (int j = 0; j < p[i].size(); j++) if (p[i][j] != p[j][i]) return 0;
    for (int i = 0; i<n; i++) if (p[i][i] != 1) return 0;
    vector<vector<int>> b(n, vector<int>(n, 0));
    vector<vector<int>> cmp;
    for (int i = 0; i < n; i++) {
        int c = -1;
        for (int j = 0; j < cmp.size(); j++) {
            for (int x: cmp[j]) {
                if (p[i][x]) c = j;
            }
        }
        for (int j = 0; j < cmp.size(); j++) {
            for (int x: cmp[j]) {
                if ((p[i][x]!=0)  ^ (j==c)) return 0;
            }
        }
        if (c==-1) cmp.push_back({i}); else cmp[c].push_back(i);
    }
    for (auto cm: cmp) if (!solve(p, cm, b)) return 0;
    build(b);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int solve(std::vector<std::vector<int> >&, std::vector<int>&, std::vector<std::vector<int> >&)':
supertrees.cpp:12:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         for (int j = 0; j < cmp.size(); j++) {
      |                         ~~^~~~~~~~~~~~
supertrees.cpp:17:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         for (int j = 0; j < cmp.size(); j++) {
      |                         ~~^~~~~~~~~~~~
supertrees.cpp:29:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int i=0; i<cm.size()-1; i++) {
      |                       ~^~~~~~~~~~~~
supertrees.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int j=0; j<cmp.size()-1; j++) {
      |                   ~^~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:47:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0; i < n; i++) for (int j = 0; j < p[i].size(); j++) if (p[i][j] != p[j][i]) return 0;
      |                                                 ~~^~~~~~~~~~~~~
supertrees.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int j = 0; j < cmp.size(); j++) {
      |                         ~~^~~~~~~~~~~~
supertrees.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int j = 0; j < cmp.size(); j++) {
      |                         ~~^~~~~~~~~~~~

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