Submission #301525

#	Time	Username	Problem	Language	Result	Execution time	Memory
301525		kevinsogo	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	282 ms	26360 KiB

supertrees

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

vector<int> get_comp(const vector<vector<int>>& adj, vector<bool>& vis, int s) {
    assert(!vis[s]);
    vis[s] = true;
    vector<int> que(1, s);
    for (int f = 0; f < que.size(); f++) {
        int i = que[f];
        assert(vis[i]);
        for (int j : adj[i]) {
            if (!vis[j]) {
                vis[j] = true;
                que.push_back(j);
            }
        }
    }
    return que;
}


int construct(vector<vector<int>> p) {
    int n = p.size();
    vector<vector<int>> ans(n, vector<int>(n));
    vector<vector<int>> adjtree(n), adjcycl(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 3) return 0;
            if (p[i][j] == 1) adjtree[i].push_back(j);
        }
    }

    vector<vector<int>> trees;
    vector<int> roots;
    vector<bool> vis(n);
    for (int s = 0; s < n; s++) {
        if (!vis[s]) {
            trees.push_back(get_comp(adjtree, vis, s));
            roots.push_back(trees.back().back());
        }
    }

    for (int t1 = 0; t1 < trees.size(); t1++) {
        for (int t2 = 0; t2 < trees.size(); t2++) {
            int target = p[roots[t1]][roots[t2]];
            if (target == 0 && t1 == t2) return 0;
            if (target == 1 && t1 != t2) return 0;
            if (target == 2 && t1 == t2) return 0;
            for (int i1 : trees[t1]) for (int i2 : trees[t2]) {
                if (p[i1][i2] != target) return 0;
            }
        }
    }

    // build trees
    for (auto& tree : trees) {
        for (int i = 1; i < tree.size(); i++) {
            ans[tree[0]][tree[i]] = 1;
        }
    }

    // build cycles
    for (int i : roots) for (int j : roots) {
        if (p[i][j] == 2) adjcycl[i].push_back(j);
    }
    vis = vector<bool>(n);
    for (int s : roots) {
        if (!vis[s]) {
            vector<int> cycle = get_comp(adjcycl, vis, s);
            for (int i : cycle) for (int j : cycle) {
                if (i != j && p[i][j] != 2) return 0;
            }
            if (cycle.size() > 1) {
                for (int i = 0, j = cycle.size() - 1; i < cycle.size(); j = i++) {
                    ans[cycle[i]][cycle[j]] = 1;
                }
            }
            if (cycle.size() == 2) return 0;
        }
    }

    // fix grid
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans[i][j] |= ans[j][i];
            ans[j][i] |= ans[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        ans[i][i] = 0;
    }

    build(ans);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'std::vector<int> get_comp(const std::vector<std::vector<int> >&, std::vector<bool>&, int)':
supertrees.cpp:9:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int f = 0; f < que.size(); f++) {
      |                     ~~^~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:44:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int t1 = 0; t1 < trees.size(); t1++) {
      |                      ~~~^~~~~~~~~~~~~~
supertrees.cpp:45:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int t2 = 0; t2 < trees.size(); t2++) {
      |                          ~~~^~~~~~~~~~~~~~
supertrees.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int i = 1; i < tree.size(); i++) {
      |                         ~~^~~~~~~~~~~~~
supertrees.cpp:75:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |                 for (int i = 0, j = cycle.size() - 1; i < cycle.size(); j = i++) {
      |                                                       ~~^~~~~~~~~~~~~~

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