Submission #400105

#	Time	Username	Problem	Language	Result	Execution time	Memory
400105		luisgalan	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	369 ms	24188 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;
    }

    bool possible = true;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 1) {
                connect(i, j, trees);
            } else if (find(i, trees) == find(j, trees)) {
                possible = false;
            }
            if (p[i][j] > 0) {
                connect(i, j, components);
            } else if (find(i, components) == find(j, components)) {
                possible = false;
            }
        }
    }

    // for (int i = 0; i < n; i++) {
    //     cerr << trees[i] << ", ";
    // }
    // cerr << endl;
    // for (int i = 0; i < n; i++) {
    //     cerr << components[i] << ", ";
    // }
    // cerr << endl;

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

    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];
        if (cycle.size() <= 2) continue;
        for (int j = 0; j < cycle.size(); j++) {
            int a = cycle[j];
            int b = cycle[(j + 1) % cycle.size()];
            result[a][b] = 1;
            result[b][a] = 1;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (find(i, components) == find(j, components)) {
                if (find(i, trees) == find(j, trees)) {
                    possible = possible && p[i][j] == 1;
                } else {
                    possible = possible && p[i][j] == 2;
                    possible = possible && (size[find(i, components)] > 2);
                    // debug(i);
                    // debug(find(i, trees));
                    // debug(size[find(i, trees)]);
                }
            } else {
                possible = possible && p[i][j] == 0;
            }
        }
    }

    if (possible) {
        build(result);
    }
    return possible;
}

// 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

// impossibility check:
// verify that all pairs (a, b) in the same tree have p[a][b] = 1
// verify that all pairs (a, b) in different trees have p[a][b] = 2

Compilation message (stderr)

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

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