Submission #927648

#	Time	Username	Problem	Language	Result	Execution time	Memory
927648		haxorman	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	191 ms	22188 KiB

supertrees

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

const int mxN = 1007;

int dsu[mxN];
bool mark[mxN], done[mxN];
vector<int> cmp[mxN];

int find(int x) {
    return dsu[x] < 0 ? x : dsu[x] = find(dsu[x]);
}

bool unite(int x, int y) {
    x = find(x), y = find(y);

    if (x == y) {
        return false;
    }

    if (dsu[x] > dsu[y]) {
        swap(x, y);
    }
    dsu[x] += dsu[y];
    dsu[y] = x;

    return true;
}

int construct(vector<vector<int>> p) {
	int n = p.size();
    memset(dsu, -1, sizeof(dsu));
    vector<vector<int>> ans(n, vector<int>(n));
    
    for (int i = 0; i < n; ++i) {
        cmp[i].push_back(i);
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (p[i][j] == 2) {
                int x = find(i), y = find(j);
                if (x != y) {
                    bool ok = true;
                    for (auto u : cmp[x]) {
                        for (auto v : cmp[y]) {
                            ok &= (p[u][v] == 2);
                        }
                    }
                    
                    if (ok) {
                        if (dsu[x] > dsu[y]) {
                            swap(x, y);
                        }

                        unite(x, y);
                        for (auto c : cmp[y]) {
                            cmp[x].push_back(c);
                        }
                    }
                }
            } 
        }
    }

    for (int i = 0; i < n; ++i) {
        int x = find(i);
        if (done[x] || cmp[x].size() <= 2) {
            continue;
        }
        done[x] = true;
    
        /*
        cout << x << "\n";
        for (auto c : cmp[x]) {
            cout << c << ' ';
        }
        cout << "\n";
        */

        for (int j = 0; j < cmp[x].size() - 1; ++j) {
            mark[cmp[x][j]] = true;
            ans[cmp[x][j]][cmp[x][j+1]] = ans[cmp[x][j+1]][cmp[x][j]] = 1;
        }
        mark[cmp[x].back()] = true;
        ans[cmp[x][0]][cmp[x].back()] = ans[cmp[x].back()][cmp[x][0]] = 1;
    }

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (i != j && p[i][j] == 1) {
                if (mark[i] && mark[j]) {
                    int x = find(i), y = find(j);

                    if (x == y) {
                        return 0;
                    }
                    
                    bool swp = false;
                    if (dsu[x] > dsu[y]) {
                        swap(x, y);
                        swp = true;
                    }

                    for (auto c : cmp[y]) {
                        if ((swp ? c != i : c != j)) {
                            cmp[x].push_back(c);
                        }
                    }

                    if (swp) {
                        mark[i] = false;
                    }
                    else {
                        mark[j] = false;
                    }
                }
                //assert(!(mark[i] && mark[j]));
                

                if (unite(i, j)) {
                    ans[i][j] = ans[j][i] = 1;
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        int x = find(i);
        if (done[x] || cmp[x].size() <= 2) {
            continue;
        }
        done[x] = true;
    
        /*
        cout << x << "\n";
        for (auto c : cmp[x]) {
            cout << c << ' ';
        }
        cout << "\n";
        */

        for (int j = 0; j < cmp[x].size() - 1; ++j) {
            ans[cmp[x][j]][cmp[x][j+1]] = ans[cmp[x][j+1]][cmp[x][j]] = 1;
        }
        ans[cmp[x][0]][cmp[x].back()] = ans[cmp[x].back()][cmp[x][0]] = 1;
    }
    build(ans);
	return 1;
}

Compilation message (stderr)

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

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