Submission #362540

#	Time	Username	Problem	Language	Result	Execution time	Memory
362540		valerikk	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	259 ms	28140 KiB

supertrees

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

const int N = 1007;

vector<int> g[N];
bool vis[N];
int col[N];
vector<int> comp;
int par[N];

int find_par(int v) {
    return par[v] == v ? v : par[v] = find_par(par[v]);
}

bool unite(int v, int u) {
    v = find_par(v);
    u = find_par(u);
    par[v] = u;
    return v != u;
}

void dfs(int v, int clr) {
    vis[v] = true;
    col[v] = clr;
    comp.push_back(v);
    for (int u : g[v]) {
        if (!vis[u]) dfs(u, clr);
    }
}


int construct(vector<vector<int>> p) {
    int n = p.size();
    for (int i = 0; i < n; i++) g[i].clear();
    for (int i = 0; i < n; i++) {
        if (p[i][i] != 1) return 0;
        for (int j = 0; j < i; j++) {
            if (p[i][j] != p[j][i]) return 0;
            if (p[i][j] == 3) return 0;
            if (p[i][j] > 0) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
    vector<vector<int>> b(n, vector<int>(n, 0));
    auto add_edge = [&](int v, int u) {
        b[v][u] = b[u][v] = 1;
    };
    for (int i = 0; i < n; i++) vis[i] = false, col[i] = -1;
    for (int st = 0; st < n; st++) {
        if (!vis[st]) {
            comp = {};
            dfs(st, st);
            bool ok = true;
            for (int v : comp) {
                for (int u : comp) ok &= p[v][u] > 0;
                for (int i = 0; i < n; i++) {
                    if (col[i] != col[v]) ok &= p[v][i] == 0;
                }
            }
            if (!ok) return 0;
            bool has = false;
            for (int v : comp) {
                for (int u : comp) has |= p[v][u] == 2;
            }
            if (has) {
                for (int i = 0; i < n; i++) par[i] = i;
                for (int v : comp) {
                    for (int u : comp) {
                        if (p[v][u] == 1) unite(v, u);
                    }
                }
                for (int v : comp) find_par(v);
                vector<int> arr;
                for (int v : comp) arr.push_back(find_par(v));
                sort(arr.begin(), arr.end());
                arr.erase(unique(arr.begin(), arr.end()), arr.end());
                if (arr.size() < 3) return 0;
                vector<vector<int>> arrs(arr.size());
                for (int v : comp) {
                    arrs[lower_bound(arr.begin(), arr.end(), find_par(v)) - arr.begin()].push_back(v);
                }
                for (int i = 0; i < arr.size(); i++) {
                    for (int j = 0; j + 1 < arrs[i].size(); j++) add_edge(arrs[i][j], arrs[i][j + 1]);
                }
                for (int i = 0; i < arr.size(); i++) add_edge(arr[i], arr[(i + 1) % (int)arr.size()]);
            } else {
                for (int i = 0; i + 1 < comp.size(); i++) add_edge(comp[i], comp[i + 1]);
            }
        }
        build(b);
        return 1;
    }
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:86:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |                 for (int i = 0; i < arr.size(); i++) {
      |                                 ~~^~~~~~~~~~~~
supertrees.cpp:87:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |                     for (int j = 0; j + 1 < arrs[i].size(); j++) add_edge(arrs[i][j], arrs[i][j + 1]);
      |                                     ~~~~~~^~~~~~~~~~~~~~~~
supertrees.cpp:89:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |                 for (int i = 0; i < arr.size(); i++) add_edge(arr[i], arr[(i + 1) % (int)arr.size()]);
      |                                 ~~^~~~~~~~~~~~
supertrees.cpp:91:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                 for (int i = 0; i + 1 < comp.size(); i++) add_edge(comp[i], comp[i + 1]);
      |                                 ~~~~~~^~~~~~~~~~~~~
supertrees.cpp:48:47: warning: control reaches end of non-void function [-Wreturn-type]
   48 |     vector<vector<int>> b(n, vector<int>(n, 0));
      |                                               ^

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