Submission #953264

#	Time	Username	Problem	Language	Result	Execution time	Memory
953264		Desh03	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	188 ms	22020 KiB

supertrees

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

using namespace std;

int construct(vector<vector<int>> p) {
    int n = p.size();
    vector<bool> vis(n);
    vector<vector<int>> b(n, vector<int> (n));
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        queue<int> q;
        q.push(i);
        vector<int> nodes;
        bool two = 0, three = 0;
        vector<bool> vis_(n);
        while (q.size()) {
            int u = q.front();
            q.pop();
            if (vis[u]) continue;
            vis[u] = vis_[u] = 1;
            nodes.push_back(u);
            for (int j = 0; j < n; j++) {
                if (p[i][j] == 2) two = 1;
                if (p[i][j] == 3) three = 1;
                if (vis[j] && !vis_[j]) return 0;
                if (!vis[j] && p[i][j]) {    
                    q.push(j);
                }
            }
        }
        for (int j = 0; j < nodes.size(); j++) {
            for (int k = j + 1; k < nodes.size(); k++) {
                if (!p[nodes[j]][nodes[k]]) {
                    return 0;
                }
            }
        }
        if (two && three) return 0;
        vector<vector<int>> trees;
        vector<bool> vis2(n);
        for (int u : nodes) {
            if (vis2[u]) continue;
            trees.push_back({});
            queue<int> q2;
            q2.push(u);
            while (q2.size()) {
                int v = q2.front();
                q2.pop();
                if (vis2[v]) continue;
                vis2[v] = 1;
                trees.back().push_back(v);
                for (int j = 0; j < n; j++) {
                    if (!vis2[j] && p[v][j] == 1) {
                        q2.push(j);
                    }
                }
            }
        }
        int sz = trees.size();
        if (two && sz < 3) return 0;
        if (three && sz < 4) return 0;
        for (int j = 0; j < sz; j++) {
            for (int k = 0; k < trees[j].size(); k++) {
                for (int l = k + 1; l < trees[j].size(); l++) {
                    if (p[trees[j][k]][trees[j][l]] > 1) {
                        return 0;
                    }
                }
            }
        }
        for (int j = 0; j < sz; j++) {
            int u = trees[j].back(), v = trees[(j + 1) % sz].back();
            if (u != v) {
                b[u][v] = b[v][u] = 1;
            }
            for (int k = 0; k < trees[j].size() - 1; k++) {
                u = trees[j][k], v = trees[j][k + 1];
                b[u][v] = b[v][u] = 1;
            }
        }
        if (three) {
            b[trees[0].back()][trees[2].back()] = b[trees[2].back()][trees[0].back()] = 1;
        }
    }
    build(b);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:32:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int j = 0; j < nodes.size(); j++) {
      |                         ~~^~~~~~~~~~~~~~
supertrees.cpp:33:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             for (int k = j + 1; k < nodes.size(); k++) {
      |                                 ~~^~~~~~~~~~~~~~
supertrees.cpp:64:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for (int k = 0; k < trees[j].size(); k++) {
      |                             ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:65:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |                 for (int l = k + 1; l < trees[j].size(); l++) {
      |                                     ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:77:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             for (int k = 0; k < trees[j].size() - 1; k++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~

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