Submission #735056

#	Time	Username	Problem	Language	Result	Execution time	Memory
735056		vjudge1	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	244 ms	22324 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"

/*
    author: aykhn
    4/28/2023
*/

using namespace std;

typedef long long ll;

#define OPT ios_base::sync_with_stdio(0); \
            cin.tie(0); \
            cout.tie(0)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pss pair<long,long>
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount
#define print(v) for(int i = 0; i < v.size(); i++) cout << v[i] << " "; cout<<endl;

struct DSU
{
    vector<int> par;
    vector<vector<int>> e;

    void init(int n)
    {
        e.resize(n);
        par.resize(n);
        for (int i = 0; i < n; i++)
        {
            e[i].pb(i);
            par[i] = i;
        }
    }

    int get(int x)
    {
        if (par[x] == x) return x;
        return par[x] = get(par[x]);
    }

    bool tog(int x, int y)
    {
        return get(x) == get(y);
    }

    void unite(int x, int y)
    {
        x = get(x);
        y = get(y);

        if (x == y) return;

        if (e[x].size() < e[y].size()) swap(x, y);

        for (int a : e[y])
        {
            e[x].pb(a);
            par[a] = x;
        }

        par[y] = x;

        e[y].clear();
    }
};

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

    vector<vector<int>> b(n, vector<int> (n, 0));
    vector<int> used(n, 0);

    DSU dsu, dsu1, dsu2;
    dsu.init(n);
    dsu1.init(n);
    dsu2.init(n);

    bool flag = false;

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

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

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (p[i][j] == 2) dsu1.unite(dsu.get(i), dsu.get(j));
            else if (p[i][j] == 3) dsu2.unite(dsu.get(i), dsu.get(j));
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j) continue;
            if (dsu1.tog(i, j) && dsu2.tog(i, j) == 1) return 0;
            if (!p[i][j] && (dsu1.tog(i, j) || dsu2.tog(i, j))) return 0;
        }
    }
/*
4
1 1 1 2
1 1 2 2
1 2 1 2
2 2 2 1
*/
    for (int i = 0; i < n; i++)
    {
        int x = dsu.get(i);
        if (!used[x])
        {
            if (dsu1.e[x].size() == 2) return 0;
            if (dsu2.e[x].size() == 2 || dsu2.e[x].size() == 3) return 0;

            for (int j = 0; j + 1 < dsu.e[x].size(); j++)
            {
                b[dsu.e[x][j]][dsu.e[x][j + 1]] = 1;
                b[dsu.e[x][j + 1]][dsu.e[x][j]] = 1;
            }

            for (int j = 0; j + 1 < dsu1.e[x].size(); j++)
            {
                b[dsu1.e[x][j]][dsu1.e[x][j + 1]] = 1;
                b[dsu1.e[x][j + 1]][dsu1.e[x][j]] = 1;
            }

            for (int j = 0; j + 1 < dsu2.e[x].size(); j++)
            {
                b[dsu2.e[x][j]][dsu2.e[x][j + 1]] = 1;
                b[dsu2.e[x][j + 1]][dsu2.e[x][j]] = 1;
            }

            if (dsu1.e[x].size() >= 3)
            {
                b[dsu1.e[x][dsu1.e[x].size() - 1]][dsu1.e[x][0]] = 1;
                b[dsu1.e[x][0]][dsu1.e[x][dsu1.e[x].size() - 1]] = 1;
            }
            if (dsu2.e[x].size() >= 4)
            {
                b[dsu2.e[x][dsu2.e[x].size() - 1]][dsu2.e[x][0]] = 1;
                b[dsu2.e[x][0]][dsu2.e[x][dsu2.e[x].size() - 1]] = 1;
                
                b[dsu2.e[x][dsu2.e[x].size() - 1]][dsu2.e[x][1]] = 1;
                b[dsu2.e[x][1]][dsu2.e[x][dsu2.e[x].size() - 1]] = 1;
            }

        }
    }
    for (int i = 0; i < n; i++) b[i][i] = 0;
    build(b);

    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:142:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |             for (int j = 0; j + 1 < dsu.e[x].size(); j++)
      |                             ~~~~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:148:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |             for (int j = 0; j + 1 < dsu1.e[x].size(); j++)
      |                             ~~~~~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:154:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |             for (int j = 0; j + 1 < dsu2.e[x].size(); j++)
      |                             ~~~~~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:90:10: warning: unused variable 'flag' [-Wunused-variable]
   90 |     bool flag = false;
      |          ^~~~

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