Submission #927694

#	Time	Username	Problem	Language	Result	Execution time	Memory
927694		haxorman	Connecting Supertrees (IOI20_supertrees)	C++14	96 / 100	187 ms	23732 KiB

supertrees

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

const int mxN = 1007;

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

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

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

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

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

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

    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][0].push_back(i);
        cmp[i][1].push_back(i);
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (p[i][j] == 1) {
                if (unite(i, j, 0)) {
                    ans[i][j] = ans[j][i] = 1;
                }
            } 
        }
    }
    
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (p[i][j] == 2) {
                int x = find(i, 0), y = find(j, 0);
                if (x == y) {
                    return 0;
                }

                if (find(x, 1) == find(y, 1)) {
                    continue;
                }

                for (auto u : cmp[x][0]) {
                    for (auto v : cmp[y][0]) {
                        if (p[u][v] != 2) {
                            return 0;
                        }
                    }
                }
                unite(x, y, 1);
            }
        }
    }

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

            if (p[i][j] == 1 && x != y && find(x, 1) == find(y,1)) {
                return 0;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        int x = find(i, 0);
        int z = find(x, 1);
        if (done[z] || cmp[z][1].size() == 1) {
            continue;
        }

        if (cmp[z][1].size() == 2) {
            return 0;
        } 

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

Compilation message (stderr)

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

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