Submission #1220057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220057		omsincoconut	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	124 ms	22264 KiB

supertrees

#include <bits/stdc++.h>

using namespace std;

void build(vector<vector<int>> b);

int construct(vector<vector<int>> p) {
    for (vector<int> v : p) for (int i : v) if (i == 3) return 0;
    int n = p.size();

    int comp[n], comp_cnt = 0;
    vector<vector<int>> comp_member;

    bool visited[n];
    memset(visited, 0, sizeof(visited));

    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;

        queue<int> bfs;
        vector<int> curcomp;
        bfs.push(i);
        
        while (!bfs.empty()) {
            int u = bfs.front();
            bfs.pop();
            if (visited[u]) continue;
            visited[u] = true;
            comp[u] = comp_cnt;
            curcomp.push_back(u);

            for (int j = 0; j < n; j++) {
                if (p[u][j] == 1) bfs.push(j);
            }
        }

        comp_member.push_back(curcomp);
        comp_cnt++;
    }

    int comp2[n], comp_cnt2 = 0;
    vector<vector<int>> comp_member2;

    bool visited2[n];
    memset(visited2, 0, sizeof(visited2));

    for (int i = 0; i < n; i++) {
        if (visited2[i]) continue;

        queue<int> bfs;
        vector<int> curcomp;
        bfs.push(i);
        
        while (!bfs.empty()) {
            int u = bfs.front();
            bfs.pop();
            if (visited2[u]) continue;
            visited2[u] = true;
            comp2[u] = comp_cnt2;
            curcomp.push_back(u);

            for (int j = 0; j < n; j++) {
                if (p[u][j] > 0) bfs.push(j);
            }
        }

        comp_member2.push_back(curcomp);
        comp_cnt2++;
    }

    // Correctness of 0
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (p[i][j] == 0 && comp2[i] == comp2[j]) return 0;
    
    vector<vector<int>> b(n, vector<int>(n, 0));
    for (vector<int> cv : comp_member) {
        for (int i = 1; i < cv.size(); i++)
            b[cv[0]][cv[i]] = b[cv[i]][cv[0]] = 1;
    }

    for (vector<int> cv : comp_member2) {
        vector<int> loop_member;
        for (int i = 0; i < cv.size(); i++) {
            bool can = true;
            for (int j = 0; j < i; j++) {
                if (comp[cv[i]] == comp[cv[j]]) {
                    can = false;
                    break;
                }
            }
            if (can) loop_member.push_back(cv[i]);
        }

        if (loop_member.size() == 1) continue;
        if (loop_member.size() == 2) return 0;

        for (int i = 0; i < loop_member.size()-1; i++)
            b[loop_member[i]][loop_member[i+1]] = b[loop_member[i+1]][loop_member[i]] = 1;
        b[loop_member[0]][loop_member.back()] = b[loop_member.back()][loop_member[0]] = 1;
    }

    build(b);
    return 1;
}

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