Submission #526644

#	Time	Username	Problem	Language	Result	Execution time	Memory
526644		Deepesson	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	219 ms	24120 KiB

supertrees

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

///void build(std::vector<std::vector<int>> _b);

#define MAX 1005
int pai[MAX][10];
int find(int a,int b){
    if(pai[a][b]==a){
        return a;
    }
    return pai[a][b]=find(pai[a][b],b);
}
void Union(int a,int b,int c){
    a=find(a,c);
    b=find(b,c);
    pai[a][c]=b;
}
void ativar(int a,int b,std::vector<std::vector<int>>& ref){
    ref[a][b]=ref[b][a]=1;
   /// printf("Constroi %d %d\n",a,b);
}
int construct(std::vector<std::vector<int>> p) {
    std::vector<std::vector<int>> answer;
    int n = p.size();
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	for(int i=0;i!=10;++i){
        for(int j=0;j!=MAX;++j)
            pai[j][i]=j;
	}
    int N = p.size();
	bool emciclo[N]={};
    for(int i=0;i!=N;++i){
        if(!p[i][i])return 0;///Tem que ligar consigo mesmo
        for(int j=0;j!=N;++j){
            if(p[i][j]==3)return 0;///Impossivel 3 caminhos
            if(p[i][j]!=p[j][i])return 0;
            if(p[i][j]==2){///Em ciclo
                Union(i,j,1);
                emciclo[i]=emciclo[j]=1;
            }
            if(p[i][j]==1){///Conexao direta
                Union(i,j,4);
            }
            if(p[i][j]!=0){///Conectado
                Union(i,j,0);
            }
        }
    }
    ///Construir arvore
    {
        std::map<int,std::vector<int>> grupos;
        for(int i=0;i!=N;++i){
            grupos[find(i,4)].push_back(i);
        }
        for(auto&x:grupos){
            if(x.second.size()==1)continue;
            std::vector<int> copia;
            copia=x.second;
            for(int i=1;i<copia.size();++i){
                if(find(copia[0],7)==find(copia[i],7))return 0;
                    Union(copia[0],copia[i],7);
                    ativar(copia[i],copia[0],answer);
            }
        }
    }
  ///  printf("Arvores inauguradas!\n");
    ///Construir ciclos
    {
        std::map<int,std::vector<int>> grupos;
        for(int i=0;i!=N;++i){
            if(!emciclo[i])continue;
            if(find(i,7)!=i)continue;
            grupos[find(i,1)].push_back(i);
        }
        for(auto&x:grupos){
            if(x.second.size()<3)return 0;
            std::vector<int> copia;
            copia=x.second;
            for(int i=1;i<copia.size();++i){
                if(find(copia[i],7)==find(copia[i-1],7))return 0;
                Union(copia[i],copia[i-1],7);
                ativar(copia[i],copia[i-1],answer);
            }
            Union(copia[0],copia[copia.size()-1],7);
            ativar(copia[0],copia[copia.size()-1],answer);
        }
    }
    for(int i=0;i!=N;++i){
        for(int j=0;j!=N;++j){
            bool k = find(i,7)==find(j,7);
            bool u = p[i][j];
            if(k!=u)return 0;
        }
    }
    build(answer);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for(int i=1;i<copia.size();++i){
      |                         ~^~~~~~~~~~~~~
supertrees.cpp:84:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             for(int i=1;i<copia.size();++i){
      |                         ~^~~~~~~~~~~~~

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