Submission #392291

#	Time	Username	Problem	Language	Result	Execution time	Memory
392291		Enkognit	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	293 ms	23060 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
#define ll long long
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define fi first
#define se second
#define pii pair<int,int>

using namespace std;

int d[1005], T;
vector<vector<int> > b;
vector<int> c[2005], v[2005], e[2005];
bool tt[2005], tl[2005];

struct dsu
{
    ll d[2005];

    void make_sets(int h)
    {
        for (int i = 0; i < h; i++) d[i]=i;
    }

    ll find_set(int h)
    {
        if (h==d[h]) return h; else return d[h]=find_set(d[h]);
    }

    void unite_sets(int x,int y)
    {
        x=find_set(x);
        y=find_set(y);
        d[x]=y;
    }
} g, gg;


void dfs(int h)
{
    tt[h]=1;
    d[h]++;
    for (int i = 0; i < c[h].size(); i++)
        if (!tt[c[h][i]])
        {
            dfs(c[h][i]);
        }
    tt[h]=0;
}

int construct(vector<vector<int> > a)
{
    ll n=a.size();
    b.resize(n);
    for (int i = 0; i < n; i++)
        b[i].resize(n, 0);

    g.make_sets(n);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (a[i][j]==1)
                g.unite_sets(i, j); else
            if (a[i][j]==3)
                return 0;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (a[i][j]!=1 && g.find_set(i)==g.find_set(j))
            {
                return 0;
            }
    vector<ll> z;
    for (int i = 0; i < n; i++)
    {
        if (g.find_set(i)==i)
        {
            z.pb(i);
        }
        v[g.find_set(i)].pb(i);
    }

    for (int i = 0; i < z.size(); i++)
    {
        for (int u = 0; u < v[z[i]].size()-1; u++)
        {
            b[v[z[i]][u+1]][v[z[i]][u]]=1;
            b[v[z[i]][u]][v[z[i]][u+1]]=1;
            c[v[z[i]][u+1]].pb(v[z[i]][u]);
            c[v[z[i]][u]].pb(v[z[i]][u+1]);
        }
    }
    gg.make_sets(n);
    for (int i = 0; i < z.size(); i++)
        for (int j = 0; j < z.size(); j++)
        {
            ll p=-1;
            for (int u = 0; u < v[z[i]].size(); u++)
                for (int q = 0; q < v[z[j]].size(); q++)
                    if (p==-1) p=a[v[z[i]][u]][v[z[j]][q]]; else
                    if (p!=a[v[z[i]][u]][v[z[j]][q]]) return 0;
            if (p==2)
                gg.unite_sets(z[i], z[j]);
        }

    for (int i = 0; i < z.size(); i++)
        for (int j = 0; j < z.size(); j++)
    {
        ll p=-1;
        for (int u = 0; u < v[z[i]].size(); u++)
            for (int q = 0; q < v[z[j]].size(); q++)
                if (p==-1) p=a[v[z[i]][u]][v[z[j]][q]]; else
                if (p!=a[v[z[i]][u]][v[z[j]][q]]) return 0;
        if (p==0 && gg.find_set(z[i])==gg.find_set(z[j]))
            return 0;
    }

    for (int i = 0; i < z.size(); i++)
        e[gg.find_set(z[i])].pb(z[i]);

    for (int i = 0; i < z.size(); i++)
        if (gg.find_set(z[i])==z[i])
        {
            if (e[z[i]].size()==2)
            {
                return 0;
            }
            if (e[z[i]].size()==1) continue;
            for (int j = 0; j < e[z[i]].size(); j++)
            {
                ll u=(j+1)%((int)e[z[i]].size());
                b[e[z[i]][j]][e[z[i]][u]]=1;
                b[e[z[i]][u]][e[z[i]][j]]=1;
                c[e[z[i]][j]].pb(e[z[i]][u]);
                c[e[z[i]][u]].pb(e[z[i]][j]);
            }
        }

    /*for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
    }*/

    build(b);

    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void dfs(int)':
supertrees.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; i < c[h].size(); i++)
      |                     ~~^~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 0; i < z.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:88:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for (int u = 0; u < v[z[i]].size()-1; u++)
      |                         ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i = 0; i < z.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for (int j = 0; j < z.size(); j++)
      |                         ~~^~~~~~~~~~
supertrees.cpp:101:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |             for (int u = 0; u < v[z[i]].size(); u++)
      |                             ~~^~~~~~~~~~~~~~~~
supertrees.cpp:102:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |                 for (int q = 0; q < v[z[j]].size(); q++)
      |                                 ~~^~~~~~~~~~~~~~~~
supertrees.cpp:109:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (int i = 0; i < z.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:110:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for (int j = 0; j < z.size(); j++)
      |                         ~~^~~~~~~~~~
supertrees.cpp:113:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         for (int u = 0; u < v[z[i]].size(); u++)
      |                         ~~^~~~~~~~~~~~~~~~
supertrees.cpp:114:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             for (int q = 0; q < v[z[j]].size(); q++)
      |                             ~~^~~~~~~~~~~~~~~~
supertrees.cpp:121:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for (int i = 0; i < z.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:124:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for (int i = 0; i < z.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:132:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |             for (int j = 0; j < e[z[i]].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~

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