Submission #386206

#	Time	Username	Problem	Language	Result	Execution time	Memory
386206		Pichon5	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	286 ms	23420 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
//"\n"
using namespace std;
const int tam=1001;
int P0[tam];
int P1[tam];
int P2[tam];
void init(){
    for(int i=0;i<tam;i++){
        P0[i]=P1[i]=P2[i]=i;
    }
}
int find0(int a){
    if(a==P0[a])return a;
    return P0[a]=find0(P0[a]);
}
int find1(int a){
    if(a==P1[a])return a;
    return P1[a]=find1(P1[a]);
}
int find2(int a){
    if(a==P2[a])return a;
    return P2[a]=find2(P2[a]);
}
void union0(int a,int b){
    a=find0(a);b=find0(b);
    P0[a]=b;
}
void union1(int a,int b){
    a=find1(a);b=find1(b);
    P1[a]=b;
}
void union2(int a,int b){
    a=find2(a);b=find2(b);
    P2[a]=b;
}

int construct(vector<vi> p){
    init();
	int n = p.size();
	vector<vector<int> > res(n,vector<int>(n,0));
	for(int i=0;i<n;i++){
        for(int l=0;l<n;l++){
            if(p[i][l]==3)return 0;
            if(p[i][l]!=0){
                union0(i,l);
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int l=i+1;l<n;l++){
            if(p[i][l]==0 && find0(i)==find0(l)){
                return 0;
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int l=i+1;l<n;l++){
            if(p[i][l]==1){
                union1(i,l);
            }
        }
    }
    for(int i=0;i<n;i++){
        int v=find1(i);
        if(i!=v)res[i][v]=res[v][i]=1;
        for(int l=i+1;l<n;l++){
            if(p[i][l]==2 && find1(i)==find1(l)){
                return 0;
            }
            if(p[i][l]==2){
                union2(find1(i),find1(l));
            }
        }
    }
    vector<vi>G(n+1);
    for(int i=0;i<n;i++){
        int e=find2(i);
        G[e].pb(i);
    }
    for(int i=0;i<n;i++){
        if(G[i].size()<=1)continue;
        if(G[i].size()==2)return 0;
        int u,v;
        for(int l=0;l<G[i].size()-1;l++){
            u=G[i][l],v=G[i][l+1];
            res[u][v]=res[v][u]=1;
        }
        u=G[i][0],v=G[i][G[i].size()-1];
        res[u][v]=res[v][u]=1;
    }
    build(res);
	return 1;


}
/*
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

4
0 2 2 2
2 0 2 2
2 2 0 2
2 2 2 0
*/
//que no haya p[i][j]=3
//1° que no haya un p[i][j] en los mega conjuntos
//2° saco los conjuntos p[i][j]=1
//3° que no haya p[i][j]=2 en los conjuntos de 1
//ahora ya puedo tomar los arboles como un solo nodo 
//pq tengo asegurado que si es que lo quiero conectar con otro arbol
//todos los nodos de mi arbol con los del otro igual a 2 por punto 3°
//4° intento hacer ciclos con en subtask 2/3
//terminado 100 pts izi


//IMPORTANTE
//puedo hacer el punto cuatro porque tengo garantizado que si un nod quiere ciclo con otro
//todos los nodos del arbol igual quieren pq si no pertenecerian al mismo arbol o ya hubiese retornado 0 en el punto 1

Compilation message (stderr)

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

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