Submission #1211510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211510		fafnir	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	115 ms	22256 KiB

supertrees

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

class DSU {
    public:
        DSU(int n) {
            m_parent.resize(n);
            iota(m_parent.begin(), m_parent.end(), 0);
        }

        int find(int v) {
            if (v == m_parent[v]) {return v;}
            int ans = find(m_parent[v]);
            m_parent[v] = ans;
            return ans;
        }

        void unionSets(int a, int b) {
            a = find(a);
            b = find(b);
            if (a != b) {
                m_parent[b] = a;
            }
        }

    private:
        vector<int> m_parent;
};


// #define LOCAL

#ifdef LOCAL
void build(vector<vector<int>> p) {
    cout << 1 << '\n';
    for (auto& row : p) {
        for (auto& el : row) cout << el << ' ';
        cout << '\n';
    }
}
#else
void build(vector<vector<int>> p);
#endif


// p: requirements
// Return 
//      0 --> Impossible to construct
//      1 --> Possible and make call to build
int construct(vector<vector<int>> p) {
    
    const int n = p.size();

    DSU dsu{n};

    for (int i = 0; i < n; ++i) {
        for (int j = i+1; j < n; ++j) {
            if (p[i][j]) {
                dsu.unionSets(i, j);
            }
        }
    }

    unordered_map<int, set<int>> groups;
    vector<int> used(n, 0);

    for (int i = 0; i < n; ++i) {
        int repr = dsu.find(i);
        used[repr] = 1;
        groups[repr].insert(i);
    }

    bool poss = true;

    vector<vector<int>> answer(n, vector<int>(n,0));
    for (auto& [repr, grp] : groups) {
        const int m = grp.size();
        vector<int> elems(grp.begin(), grp.end());
        
        for (int i = 0; i < m-1; ++i) {
            int s = elems[i];
            int e = elems[i+1];

            if (p[s][e] == 0) {poss = false; break;}

            if (s != e) {
                answer[s][e] = 1;
                answer[e][s] = 1;
            }

            if (p[elems[m-1]][elems[0]] == 0) {poss = false;}
        }

        if (!poss) {break;}
    }
    
    if (poss) {
        build(answer);
        return 1;
    } else {
        return 0;
    }
}

#ifdef LOCAL
int32_t main(int argc, char** argv) {

    assert (argc == 3);

    freopen(argv[1], "r", stdin);
    freopen(argv[2], "w", stdout);


    vector<vector<int>> p;
    int n;
    cin >> n;

    p.resize(n);
    for (auto& e : p) {
        vector<int> row(n);
        for (auto& el : row) cin >> el;
        e = row;
    }

    construct(p);

    return 0;
}
#endif

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