Submission #953601

#	Time	Username	Problem	Language	Result	Execution time	Memory
953601		Desh03	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	169 ms	24404 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 (!vis[j] && p[u][j]) {    
                    q.push(j);
                }
            }
        }
        for (int u : nodes) {
            for (int j = 0; j < n; j++) {
                if ((!vis_[j] && p[u][j]) || (vis_[j] && !p[u][j])) {
                    return 0;
                } else if (vis_[j]) {
                    if (p[u][j] == 3) {
                        three = 1;
                    }
                    if (p[u][j] == 2) {
                        two = 1;
                    }
                }
            }
        }
        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 k = j + 1; k < sz; k++) {
                for (int u : trees[j]) {
                    for (int v : trees[k]) {
                        if ((two && p[u][v] != 2) || (three && p[u][v] != three)) {
                            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:68:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for (int k = 0; k < trees[j].size(); k++) {
      |                             ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:69:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |                 for (int l = k + 1; l < trees[j].size(); l++) {
      |                                     ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:90:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             for (int k = 0; k < trees[j].size() - 1; 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