Submission #1195301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195301		yoavL	Connecting Supertrees (IOI20_supertrees)	C++20	40 / 100	118 ms	22236 KiB

supertrees

#include "supertrees.h"

#include <bits/stdc++.h>

#define rep(i, s, e) for(int i = s; i < e; i++)
#define pr(x) cout << x << endl
#define wpr(x) cout << #x << "=" << x << endl

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using pi = pair<int, int>;
using vpi = vector<pi>;
using vvpi = vector<vpi>;

template<class A>
ostream &operator<<(ostream &os, const vector<A> &arr) {
    if (arr.empty()) {
        return os << "[]";
    }
    os << "[";
    rep(i, 0, arr.size()) {
        os << arr[i] << ",]"[i == arr.size() - 1];
    }
    return os;
}

template<class A, class B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
    return os << "{" << p.first << "," << p.second << "}";
}

/**
 * Solution:
 * 1. First split to C.Cs, and check validity.
 * 2. For each C.C:
 *      1. Find cliques of 1's.
 *      2. Create lines of all of those cliques.
 *      3. Merge them using a representor to a circle, if there are at least 3 lines.
 *
 */


bool handle_comp(vvi &p, vvi &g, vi &comp) {
    int sz = comp.size();
    vi color(sz, -1);
    int cur_col = 0;
    vvi cc;
    rep(i, 0, sz) {
        if (color[i] >= 0) continue;
        color[i] = cur_col++;
        cc.push_back({comp[i]});
        rep(j, i+1, sz) {
            if (p[comp[i]][comp[j]] == 1) {
                color[j] = color[i];
                cc.back().push_back(comp[j]);
            }
        }
    }

    int valid = 1;
    rep(i, 0, sz) {
        rep(j, 0, sz) {
            int u = comp[i], v = comp[j];

            // If they are in the same C.C, p should be 1. Otherwise, 2.
            if (color[i] == color[j]) {
                valid &= (p[u][v] == 1);
            } else {
                valid &= (p[u][v] == 2);
            }
        }
    }

    valid &= (cc.size() != 2);
    if (!valid) return 0;
    // Create lines:
    for (auto &line: cc) {
        rep(i, 1, line.size()) {
            g[line[i]][line[i - 1]] = g[line[i - 1]][line[i]] = 1;
        }
    }
    if (cc.size() >= 3) {
        // Merge lines:
        rep(i, 0, cc.size()) {
            int u = cc[(i + 1) % sz][0], v = cc[i][0];
            g[u][v] = g[v][u] = 1;
        }
    }
    return 1;
}


int construct(vector<vector<int> > p) {
    int n = p.size();
    rep(i, 0, n) {
        assert(p[i][i] == 1);
    }
    vvi g(n, vi(n, 0));
    vi color(n, -1);
    int cur_col = 0;
    vvi cc;
    rep(i, 0, n) {
        if (color[i] >= 0) continue;
        color[i] = cur_col++;
        cc.push_back({i});
        rep(j, i+1, n) {
            if (p[i][j] >= 1) {
                color[j] = color[i];
                cc.back().push_back(j);
            }
        }
    }
    rep(i, 0, n) {
        rep(j, 0, n) {
            if ((p[i][j] > 0) ^ (color[i] == color[j])) {
                return 0;
            }
        }
    }
    for (auto &comp: cc) {
        if (!handle_comp(p, g, comp)) return 0;
    }
    build(g);
    return 1;
}

/*
1
1

2
1 1
1 1

3
1 1 1
1 1 1
1 1 1

3
1 1 1
1 1 0
1 0 1

3
1 0 1
0 1 0
1 0 1


3
1 2 2
2 1 2
2 2 1

4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

4
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1

*/

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