Submission #430684

#	Time	Username	Problem	Language	Result	Execution time	Memory
430684		MeGustaElArroz23	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	269 ms	22212 KiB

supertrees

//////////////////

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

vi comp;

int find(int x){
    if (comp[x]==x) return x;
    int sol=find(comp[x]);
    comp[x]=sol;
    return sol;
}
void unite(int a, int b){
    a=find(a);
    b=find(b);
    comp[a]=b;
}

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

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

    vvi res(n,vi(n,0));

    comp=vi(n);
    for (int i=0;i<n;i++) comp[i]=i;

	for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            if (p[i][j]==1){
                if (find(i)!=find(j)){
                    unite(i,j);
                    res[i][j]=1;
                    res[j][i]=1;
                }
            }
        }
    }

    vi nodes;
    for (int i=0;i<n;i++){
        if (comp[i]==i) nodes.push_back(i);
    }

    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            if (find(i)==find(j) and p[i][j]!=1) return 0;
        }
    }
    //hemos acabado con los de 1

    for (int i:nodes){
        for (int j:nodes){
            if (p[i][j]==2){
                if (find(i)!=find(j)){
                    unite(i,j);
                }
            }
        }
    }

    vvi ciclos(n);
    for (int i:nodes){
        ciclos[find(i)].push_back(i);
    }

    for (int i:nodes){
        if (ciclos[i].size()<=1) continue;
        else if (ciclos[i].size()==2) return 0;
        else{
            for (int j=0;j<ciclos[i].size();j++){
                res[ciclos[i][j]][ciclos[i][(j+1)%ciclos[i].size()]]=1;
                res[ciclos[i][(j+1)%ciclos[i].size()]][ciclos[i][j]]=1;
            }
        }
        for (int j:ciclos[i]){
            for (int k:ciclos[i]){
                //cerr<< j << ' ' << k << '\n';
                if (j!=k and p[j][k]!=2) return 0;
            }
        }
    }

    build(res);

	return 1;

    //comprobar si funciona
    //mejorar complejidad dsu
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:83:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for (int j=0;j<ciclos[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