Submission #619715

#	Time	Username	Problem	Language	Result	Execution time	Memory
619715		mosiashvililuka	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	293 ms	30448 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
#include <vector>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[1009][1009],msh[1009],zm[1009],bo[1009][1009],p[1009],pi,MSH[1009],ZM[1009];
vector <int> v[1009],V[1009];
vector <vector <int> > ANS;
int fnd(int q){
    if(msh[q]==0) return q; else return msh[q]=fnd(msh[q]);
}
void mrg(int q, int w){
    q=fnd(q);w=fnd(w);
    if(q==w) return;
    if(zm[q]<zm[w]) swap(q,w);
    msh[w]=q;
    if(zm[q]==zm[w]) zm[q]++;
}





int FND(int q){
    if(MSH[q]==0) return q; else return MSH[q]=fnd(MSH[q]);
}
void MRG(int q, int w){
    q=FND(q);w=FND(w);
    if(q==w) return;
    if(ZM[q]<ZM[w]) swap(q,w);
    MSH[w]=q;
    if(ZM[q]==ZM[w]) ZM[q]++;
}
int construct(vector <vector <int> > Pp) {
    a=Pp.size();
    for(i=1; i<=a; i++){
        for(j=1; j<=a; j++){
            f[i][j]=Pp[i-1][j-1];
            if(f[i][j]==3) return 0;
        }
    }
    //check

    for(i=1; i<=a; i++){
        for(j=i+1; j<=a; j++){
            if(f[i][j]!=0) mrg(i,j);
        }
    }
    for(i=1; i<=a; i++){
        for(j=i+1; j<=a; j++){
            if(fnd(i)==fnd(j)){
                if(f[i][j]==0) return 0;
            }
        }
    }
    for(i=0; i<=a+1; i++){
        msh[i]=zm[i]=0;
    }

    //
    for(i=1; i<=a; i++){
        for(j=i+1; j<=a; j++){
            if(f[i][j]==1) mrg(i,j);
        }
    }
    for(i=1; i<=a; i++){
        v[fnd(i)].push_back(i);
    }
    for(i=1; i<=a; i++){
        for(ii=0; ii<v[i].size(); ii++){
            for(jj=ii+1; jj<v[i].size(); jj++){
                c=v[i][ii];d=v[i][jj];
                if(f[c][d]!=1) return 0;
            }
        }
    }
    for(i=1; i<=a; i++){
        if(v[i].size()==0) continue;
        for(jj=1; jj<v[i].size(); jj++){
            c=v[i][jj-1];d=v[i][jj];
            bo[c][d]=bo[d][c]=1;
        }
        pi++;p[pi]=v[i][0];
    }
    for(i=1; i<=pi; i++){
        for(j=i+1; j<=pi; j++){
            if(f[p[i]][p[j]]==2) MRG(p[i],p[j]);
        }
    }
    for(i=1; i<=pi; i++){
        V[FND(p[i])].push_back(p[i]);
    }
    for(i=1; i<=a; i++){
        if(V[i].size()==2) return 0;
        if(V[i].size()<=1) continue;
        for(ii=0; ii<V[i].size(); ii++){
            for(jj=ii+1; jj<V[i].size(); jj++){
                c=V[i][ii];d=V[i][jj];
                if(f[c][d]!=2) return 0;
            }
        }
        for(jj=0; jj<V[i].size(); jj++){
            if(jj!=0) c=V[i][jj-1]; else c=V[i][V[i].size()-1];
            d=V[i][jj];
            bo[c][d]=bo[d][c]=1;
        }
    }
    ANS.resize(a);
    for(i=0; i<a; i++) ANS[i].resize(a);
    for(i=0; i<a; i++){
        for(j=0; j<a; j++){
            ANS[i][j]=bo[i+1][j+1];
        }
    }
    build(ANS);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:69:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(ii=0; ii<v[i].size(); ii++){
      |                   ~~^~~~~~~~~~~~
supertrees.cpp:70:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             for(jj=ii+1; jj<v[i].size(); jj++){
      |                          ~~^~~~~~~~~~~~
supertrees.cpp:78:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for(jj=1; jj<v[i].size(); jj++){
      |                   ~~^~~~~~~~~~~~
supertrees.cpp:95:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(ii=0; ii<V[i].size(); ii++){
      |                   ~~^~~~~~~~~~~~
supertrees.cpp:96:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             for(jj=ii+1; jj<V[i].size(); jj++){
      |                          ~~^~~~~~~~~~~~
supertrees.cpp:101:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for(jj=0; jj<V[i].size(); jj++){
      |                   ~~^~~~~~~~~~~~

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