Submission #317823

#	Time	Username	Problem	Language	Result	Execution time	Memory
317823		akobi	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	288 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int find_set(int u,vector<int> &p) 
{
    if (u==p[u])
        return u;
    return p[u]=find_set(p[u],p);
}
void union_set(int u,int v,vector <int> &p) 
{
    u=find_set(u,p);
    v=find_set(v,p);
    p[u]=v;
    return;
}
int n,u,v;
vector<int> p,pp,t,fix,s;
vector< vector<int> > b,g;
int construct( vector<vector<int>> a ) 
{
    n=a.size();
    for (int i=0; i<n; i++)
        p.pb(i);
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++) 
        {
            if (a[i][j]==3)
                return 0;
            if (a[i][j]>0)
                union_set(i,j,p);
        }
    for (int i=0; i<n; i++) 
        for (int j=0; j<n; j++) 
        {
            u=find_set(i,p);
            v=find_set(j,p);
            if (u==v && a[i][j]==0) 
                return 0;
        }
    for (int i=0; i<n; i++)
        g.pb(t);
    for (int i=0; i<n; i++)
    {
        u=find_set(i,p);
        g[u].pb(i);
    }
    for (int i=0; i<n; i++) 
        pp.pb(i);
    for (int i=0; i<n; i++)
        b.pb(t);
    for (int i=0; i<n; i++) 
    {
        if (g[i].empty()) 
            continue;
        for (int x=0; x<g[i].size(); x++)
            for (int y=x; y<g[i].size(); y++)
                if (a[ g[i][x] ][ g[i][y] ] == 1)
                    union_set(x, y, pp);
        
        for (int x=0; x<g[i].size(); x++)
            for (int y=x; y<g[i].size(); y++)
            {
                u=find_set(g[i][x],pp);
                v=find_set(g[i][y],pp);
                if (u==v && a[x][y]==2)
                    return 0;
            }
        for (int x=0; x<n; x++)
            fix.pb(-1);
        for (int x=0; x<g[i].size(); x++) 
        {
            u=find_set(g[i][x],pp);
            if (fix[u]!=-1) 
            {
                b[ fix[u] ][ g[i][x] ]=1;
                b[ g[i][x] ][ fix[u] ]=1; 
            }
            fix[u]=g[i][x];
            if (g[i][x]==u)
                s.pb(x);
        }
        if (s.size()==2)
            return 0;
        for (int j=1; j<s.size(); j++) 
        {
            u=s[j-1];
            v=s[j];
            b[u][v]=1;
            b[v][u]=1;
        }
        u=s[ s.size()-1 ];
        v=s[0];
        if (u!=v)
        {
            b[u][v]=1;
            b[v][u]=1;
        }
    }
    build(b);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:57:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int x=0; x<g[i].size(); x++)
      |                       ~^~~~~~~~~~~~
supertrees.cpp:58:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for (int y=x; y<g[i].size(); y++)
      |                           ~^~~~~~~~~~~~
supertrees.cpp:62:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for (int x=0; x<g[i].size(); x++)
      |                       ~^~~~~~~~~~~~
supertrees.cpp:63:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             for (int y=x; y<g[i].size(); y++)
      |                           ~^~~~~~~~~~~~
supertrees.cpp:72:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int x=0; x<g[i].size(); x++)
      |                       ~^~~~~~~~~~~~
supertrees.cpp:86:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for (int j=1; j<s.size(); j++)
      |                       ~^~~~~~~~~

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