Submission #483252

#	Time	Username	Problem	Language	Result	Execution time	Memory
483252		lukaszgniecki	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	322 ms	23172 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

#define ll long long
#define str string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

#define vc vector<char>
#define vvc vector<vc>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vvvvi vector<vvvi>
#define vll vector<ll>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define vvvvll vector<vvvll>
#define vs vector<str>
#define vvs vector<vs>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define vb vector<bool>
#define vvb vector<vb>
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
#define repi(i, a, b) for (int i = (a); i <= int(b); i++)

using namespace std;

//TODO: SOLUTION
int n;

bool contains3(vvi & paths) {
    rep(i, 0, n) {
        rep(j, 0, n) {
            if (paths[i][j] == 3)
                return true;
        }
    }
    return false;
}

bool trees_are_fine(vvi & paths, vi & treeof) {
    rep(x, 0, n) {
        rep(y, 0, n) {
            if (treeof[x] == treeof[y] && paths[x][y] != 1)
                return false;
            if (treeof[x] != treeof[y] && paths[x][y] == 1)
                return false;
        }
    }

    return true;
}

bool trees_connected(vvi & paths, vi & t1, vi & t2) {
    for (int x : t1) {
        for (int y : t2) {
            if (paths[x][y] != 2)
                return false;
        }
    }
    return true;
}

bool cycle_contains(vvi & paths, vi & cycle, vvi & trees, vi & tr) {
    for (int tidx : cycle) {
        auto & cyc_tree = trees[tidx];
        if (!trees_connected(paths, cyc_tree, tr))
            return false;
    }
    return true;
}

bool cycles_are_fine(vvi & paths, vi & cycleof, vvi & trees) {
    rep(i, 0, trees.size()) {
        rep(j, 0, trees.size()) {
            if (i == j)
                continue;
            if (cycleof[i] == cycleof[j] && !trees_connected(paths, trees[i], trees[j]))
                return false;
            if (cycleof[i] != cycleof[j] && trees_connected(paths, trees[i], trees[j]))
                return false;
        }
    }
    return true;
}

bool connect_trees(vvi & gr, vvi & trees) {
    for (auto & tr : trees) {
        rep(i, 1, tr.size()) {
            gr[tr[i]][tr[i - 1]] = gr[tr[i - 1]][tr[i]] = 1;
        }
    }
    return true;
}

bool connect_cycles(vvi & gr, vvi & cycles, vvi & trees) {
    for (auto & cyc : cycles) {
        if (cyc.size() == 2)
            return false;
        if (cyc.size() == 1)
            continue;

        rep(i, 0, cyc.size()) {
            int x = cyc[i];
            int y = cyc[(i + 1) % cyc.size()];
            gr[trees[x][0]][trees[y][0]] = gr[trees[y][0]][trees[x][0]] = 1;
        }
    }

    return true;
}

/*void build(vvi gr) {
    rep(i, 0, n) {
        rep(j, 0, n) {
            cerr << gr[i][j] << ' ';
        }
        cerr << '\n';
    }
}*/

int construct(vvi paths) {
    n = paths.size();

    // contains 3 => not possible
    if (contains3(paths))
        return 0;

    // construct maximal trees
    vvi trees;
    vi treeof(n, 0);

    rep(x, 0, n) {
        bool found_tree = false;

        rep(i, 0, trees.size()) {
            auto & tr = trees[i];
            bool this_tree = true;

            for (int y : tr) {
                if (paths[x][y] != 1) {
                    this_tree = false;
                    break;
                }
            }

            if (this_tree) {
                tr.push_back(x);
                treeof[x] = i;
                found_tree = true;
                break;
            }
        }

        if (!found_tree) {
            trees.push_back({x});
            treeof[x] = trees.size() - 1;
        }
    }

    // check if partition into trees is correct
    if (!trees_are_fine(paths, treeof))
        return 0;

    // form cycles on trees
    vvi cycles; // trees are now vertices
    vi cycleof(trees.size());

    rep(t, 0, trees.size()) {
        vi & tr = trees[t];

        bool cycle_found = false;
        rep(i, 0, cycles.size()) {
            auto & cyc = cycles[i];
            if (cycle_contains(paths, cyc, trees, tr)) {
                cycleof[t] = i;
                cyc.push_back(t);
                cycle_found = true;
            }
        }

        if (!cycle_found) {
            cycles.push_back({t});
            cycleof[t] = cycles.size() - 1;
        }
    }

    // validate cycles
    if (!cycles_are_fine(paths, cycleof, trees))
        return 0;

    // construct graph
    vvi gr(n, vi(n, 0));
    if (!connect_trees(gr, trees))
        return 0;
    if (!connect_cycles(gr, cycles, trees))
        return 0;

    // build the graph
    rep(i, 0, n) gr[i][i] = 0;
    build(gr);
    return 1;
}

/*
int main() {
    vvi p1 = {{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}};
    vvi p2 = {{1, 0}, {0, 1}};
    vvi p3 = {
            {1, 2, 2, 2, 2, 2, 0, 0, 0, 0},
            {2, 1, 1, 1, 2, 2, 0, 0, 0, 0},
            {2, 1, 1, 1, 2, 2, 0, 0, 0, 0},
            {2, 1, 1, 1, 2, 2, 0, 0, 0, 0},
            {2, 2, 2, 2, 1, 1, 0, 0, 0, 0},
            {2, 2, 2, 2, 1, 1, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 1, 1, 0, 0},
            {0, 0, 0, 0, 0, 0, 1, 1, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 1, 1},
            {0, 0, 0, 0, 0, 0, 0, 0, 1, 1}
    };
    cout << construct(p1) << endl;
    cout << construct(p2) << endl;
    cout << construct(p3) << endl;
}*/

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