Submission #1363631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1363631		yavor_ptv	Connecting Supertrees (IOI20_supertrees)	C++20	Compilation error	0 ms	0 KiB

supertrees

// SUBTASK 1 -> 6
#include <bits/stdc++.h>
#include "supertrees.h"
#include "grader.cpp"
using namespace std;

struct DSU
{
    vector<int> par, sz;

    DSU() {}

    DSU(int n)
    {
        init(n);
    }

    void init(int n)
    {
        par.resize(n);
        sz.assign(n, 1);

        iota(par.begin(), par.end(), 0);
    }

    int find_root(int u)
    {
        if (u == par[u]) return u;

        return par[u] = find_root(par[u]);
    }

    void join(int u, int v)
    {
        int r1 = find_root(u);
        int r2 = find_root(v);

        if (r1 == r2) return;

        if (sz[r1] < sz[r2]) swap(r1, r2);

        par[r2] = r1;
        sz[r1] += sz[r2];
    }
};

int construct(vector<vector<int>> p)
{
    int n = p.size();

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (p[i][j] == 3) return 0;
        }
    }

    DSU dsu(n);
    DSU dsu_1(n);

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

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            bool flag_big = dsu.find_root(i) == dsu.find_root(j);
            bool flag_1 = dsu_1.find_root(i) == dsu_1.find_root(j);

            if (p[i][j] > 0 && flag_big == 0) return 0;
            if (p[i][j] == 0 && flag_big == 1) return 0;

            if (p[i][j] == 1 && flag_1 == 0) return 0; //!
            if (p[i][j] != 1 && flag_1 == 1) return 0; //!
        }
    }

    vector<vector<int>> ans(n, vector<int>(n, 0));

    vector<vector<int>> comps_1(n);

    for (int i = 0; i < n; i++) {
        int root = dsu_1.find_root(i);
        comps_1[root].push_back(i);
    }

    for (int i = 0; i < n; i++) {
        int k = (int)comps_1[i].size();

        for (int j = 0; j < k - 1; j++) {
            int a = comps_1[i][j];
            int b = comps_1[i][j + 1];

            ans[a][b] = 1;
            ans[b][a] = 1;
        }
    }

    vector < vector<int> > comps_2(n);
    for (int i = 0; i < n; i++)
    {
        if (!comps_1[i].size()) continue;
        int bigRoot = dsu.find_root(comps_1[i][0]);
        comps_2[bigRoot].push_back(comps_1[i][0]);
    }

    for (int i = 0; i < n; i++)
    {
        int k = (int)comps_2[i].size();
        if (k < 2) continue;
        if (k == 2) return 0;

        for (int j = 0; j < k; j++)
        {
            int a = comps_2[i][j];
            int b = comps_2[i][(j + 1) % k];

            ans[a][b] = 1;
            ans[b][a] = 1;
        }
    }

    build(ans);
    return 1;
}
/*
HACK CASE:
3
1 1 2
1 1 1
2 1 1

1
0 1 0
1 0 1
0 1 0
*/

Compilation message (stderr)

/usr/bin/ld: /tmp/ccCaimkc.o: in function `build(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)':
grader.cpp:(.text+0x300): multiple definition of `build(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)'; /tmp/ccsftVD6.o:supertrees.cpp:(.text+0x300): first defined here
/usr/bin/ld: /tmp/ccCaimkc.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccsftVD6.o:supertrees.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status