Submission #400089

#	Time	Username	Problem	Language	Result	Execution time	Memory
400089		luisgalan	Connecting Supertrees (IOI20_supertrees)	C++14	46 / 100	363 ms	23916 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << (x) << endl

const int MAX_N = 1e3 + 3;

int find(int x, vector<int> &ufds) {
    return ufds[x] = (ufds[x] == x ? x : find(ufds[x], ufds));
}
void connect(int a, int b, vector<int> &ufds) {
    if (rand() % 2) swap(a, b);
    ufds[find(a, ufds)] = find(b, ufds);
}

int construct(std::vector<std::vector<int>> p) {
    int n = p.size();
    vector<vector<int>> result(n);
    fill(result.begin(), result.end(), vector<int>(n));
    if (n == 1) {
        build(result);
        return 1;
    }

    vector<int> trees(n);
    vector<int> components(n);
    for (int i = 0; i < n; i++) {
        trees[i] = i;
        components[i] = i;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 1) {
                connect(i, j, trees);
            }
            if (p[i][j] > 0) {
                connect(i, j, components);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cerr << find(i, trees) << ", ";
    }
    cerr << endl;
    for (int i = 0; i < n; i++) {
        cerr << find(i, components) << ", ";
    }
    cerr << endl;

    for (int i = 0; i < n; i++) {
        int a = find(i, trees);
        if (i == a) continue;
        result[i][a] = 1;
        result[a][i] = 1;
    }

    vector<vector<int>> cycles(n);
    set<int> visited;
    for (int i = 0; i < n; i++) {
        int t = find(i, trees);
        int c = find(i, components);
        if (!visited.count(t)) {
            cycles[c].push_back(t);
            visited.insert(t);
        }
    }

    for (int i = 0; i < n; i++) {
        vector<int> &cycle = cycles[i];
        for (int j = 0; j < cycle.size(); j++) {
            int a = cycle[j];
            int b = cycle[(j + 1) % cycle.size()];
            if (a == b) continue;
            result[a][b] = 1;
            result[b][a] = 1;
        }
    }

    build(result);
    return 1;
}

// it's easy to prove that there must be at most one cycle for st5 (and that any matrix with some p[i][j] = 2 must have a cycle)
// but we could have more than one tree
// we essentially have that some nodes are part of the cycle and then we have multiple trees rooted in one of the cycle nodes
// we could have nodes 1 2 3 and 4 where p[1][2] = 1, p[3][4] = 1 but p[2][3] = 2
// we have that p[i][j] = 2 iff the paths go through the cycle

// we essentially have a collection of trees
// if p[i][j] = 2 then node i and j must be on the same component but of different trees
// if p[i][j] = 1 then node i and j belong to the same tree
// it doesn't actually matter which node we root the tree in (ie which node we put on the cycle)
// we thus have the following algorithm:
// if p[i][j] = 1 connect them in the tree ufds
// if p[i][j] > 0 connect them in the component ufds
// for each node A in the same component connect find(A) to the cycle

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int j = 0; j < cycle.size(); j++) {
      |                         ~~^~~~~~~~~~~~~~

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