Submission #825364

#	Time	Username	Problem	Language	Result	Execution time	Memory
825364		HorizonWest	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	188 ms	24012 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
struct st
{
    vector<int> cad;
    int findf(int a)
    {
        if(a==cad[a])return a;
        else return cad[a]=findf(cad[a]);
    }
    void unionf(int a, int b){
        a=findf(a);
        b=findf(b);
        if(a!=b){
            cad[a]=b;
        }
    }
    st(int n){
        cad.resize(2*n);
        for(int i=0; i<cad.size(); i++)
            cad[i]=i;
    }
};
int construct(std::vector<std::vector<int>> cad) {
    int n = cad.size();
    std::vector<std::vector<int>> answer(n,vector<int>(n,0LL));
    st asdfg(n+1);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(cad[i][j]!=0&&i!=j)
                asdfg.unionf(i,j);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(cad[i][j]==0&&asdfg.findf(i)==asdfg.findf(j)&&i!=j)
                return 0;
    st asd(n+1);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(cad[i][j]==1&&i!=j)
                asd.unionf(i,j);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
        {
            if(cad[i][j]==2&&asd.findf(i)==asd.findf(j)&&i!=j)
                return 0;
            if(asd.cad[i]==j&&i!=j)
            {
                answer[i][j]=1;
                answer[j][i]=1;
            }
        }
    int v2[n+1]={ };
    int v[n+1]={ };
    for(int j=0; j<n; j++)
    {
        int p=asd.findf(j);
        if(v[p]==0)
        {
            int pg=p;
            v[p]=1;
            for(int i=j+1; i<n; i++)
            {
                if(v[asd.findf(i)]==0&&asdfg.findf(i)==asdfg.findf(p))
                {
                    answer[asd.findf(i)][p]=1;
                    answer[p][asd.findf(i)]=1;
                    p=asd.findf(i);
                    v[asd.findf(i)]=1;
                    v2[asdfg.findf(i)]++;
                }
            }
            if(pg!=p)
            {
                answer[pg][p]=1;
                answer[p][pg]=1;
            }
        }
 
 
    }
 
    /*for(int i=0; i<n; i++)
    {
        if(v2[asdfg.findf(i)]==1)
            return 0;
    }*/
    build(answer);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In constructor 'st::st(int)':
supertrees.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int i=0; i<cad.size(); i++)
      |                      ~^~~~~~~~~~~

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