Submission #386198

#	Time	Username	Problem	Language	Result	Execution time	Memory
386198		Pichon5	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1128 ms	391908 KiB

supertrees

#include "supertrees.h"
#include <vector>
#define vi vector<int>
#define pb push_back
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]=P1[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]){
                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(v);
        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;
    }
    construct(res);

	return 1;


}

Compilation message (stderr)

supertrees.cpp: In function 'void init()':
supertrees.cpp:12:20: warning: operation on 'P1[i]' may be undefined [-Wsequence-point]
   12 |         P0[i]=P1[i]=P1[i]=i;
      |               ~~~~~^~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int l=0;l<G[i].size()-1;l++){
      |                     ~^~~~~~~~~~~~~~
supertrees.cpp:21:17: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   21 |     return P1[a]=find1(P1[a]);
      |            ~~~~~^~~~~~~~~~~~~
supertrees.cpp:67:13: note: 'v' was declared here
   67 |         int v=find1(v);
      |             ^

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