Submission #732271

#	Time	Username	Problem	Language	Result	Execution time	Memory
732271		aykhn	Connecting Supertrees (IOI20_supertrees)	C++14	96 / 100	241 ms	22284 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), used1(n, 0), used2(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);
        }
    }
 
    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)) 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 (dsu2.e[x].size() == 2 || dsu2.e[x].size() == 3) return 0;
        if (dsu1.e[x].size() == 2) return 0;
        if (!used[x])
        {
            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;
            }
            used[x] = 1;
        }
        x = dsu2.get(i);
        if (!used1[x])
        {
            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;
            }
 
            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;
            }
            used1[x] = 1;
        }
        x = dsu2.get(i);
        if (!used2[x])
        {
            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 (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][2]][dsu2.e[x][0]] = 1;
                b[dsu2.e[x][0]][dsu2.e[x][2]] = 1;
            }
 
            used2[x] = 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:140:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |             for (int j = 0; j + 1 < dsu.e[x].size(); j++)
      |                             ~~~~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:150:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |             for (int j = 0; j + 1 < dsu1.e[x].size(); j++)
      |                             ~~~~~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:166:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |             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: 0 / 4