Submission #586027

#	Time	Username	Problem	Language	Result	Execution time	Memory
586027		John3_141592	Connecting Supertrees (IOI20_supertrees)	C++14	96 / 100	207 ms	27920 KiB

supertrees

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

using namespace std;

int dad[1006],ded[1006],asd[1003][1003];

int Find(int x){
    return x==dad[x]?x:dad[x]=Find(dad[x]);
}

void Union(int a,int b){
    a=Find(a),b=Find(b);
    if(a>b) swap(a,b);
    dad[b]=a;
}

int Find1(int x){
    return x==ded[x]?x:ded[x]=Find1(ded[x]);
}

void Union1(int a,int b){
    a=Find1(a),b=Find1(b);
    if(a>b) swap(a,b);
    ded[b]=a;
}

int construct(std::vector<std::vector<int>> p) {
	int n=p.size();
	vector <vector <int> > answer;
	bool band=false,BAND=false,FLAG=false;
	for(int i=0;i<=n;i++) dad[i]=i;
	for(int i=0;i<n;i++){
        for(int j=0;j<p[i].size();j++){
            if(p[i][j]==3) FLAG=true;
            if(p[i][j]==2) band=true;
            else if(i!=j && p[i][j]) BAND=true;
            if(p[i][j]) Union(i,j);
        }
	}
	for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j && p[i][j]!=1) return 0;
            if(!p[i][j] && Find(i)==Find(j)) return 0;
        }
	}
	if(FLAG){
        for(int i=0;i<=n;i++) ded[i]=i;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(p[i][j]==1){
                    Union1(i,j);
                }
            }
        }
        vector <int> grafo[1000];
        for(int i=0;i<n;i++){
            grafo[Find1(i)].push_back(i);
        }
        for(int i=0;i<n;i++){
            if(grafo[i].empty()) continue;
            int v=grafo[i].size();
            for(int j=0;j<v;j++) asd[i][grafo[i][j]]=asd[grafo[i][j]][i]=1;
        }
        vector <int> qwe;
        for(int i=0;i<n;i++){
            if(grafo[i].empty()) continue;
            qwe.push_back(i);
        }
        for(int i=0;i<n;i++) grafo[i].clear();
        for(auto i:qwe) grafo[Find(i)].push_back(i);
        for(int i=0;i<n;i++){
            if(grafo[i].empty()) continue;
            int v=grafo[i].size();
            if(v==2) return 0;
            for(int j=0;j<v;j++) asd[grafo[i][(j-1+v)%v]][grafo[i][j]]=asd[grafo[i][j]][grafo[i][(j-1+v)%v]]=1;
            bool mark[10];
            fill(mark,mark+7,false);
            vector <int> zxc;
            for(int j=0;j<n;j++){
                if(i!=Find(j)) continue;
                zxc.push_back(j);
            }
            for(auto j:zxc){
                for(auto k:zxc){
                    mark[p[j][k]]=true;
                }
            }
            if(mark[2] && mark[3]) return 0;
            if(mark[3]){
                if(v==3) return 0;
                bool vis=false;
                for(auto j:grafo[i]){
                    for(auto k:grafo[i]){
                        if(!asd[j][k] && j!=k){
                            asd[j][k]=asd[k][j]=1;
                            vis=true;
                            break;
                        }
                    }
                    if(vis) break;
                }
            }
        }
        for(int i=0;i<n;i++){
            vector <int> qwe;
            for(int j=0;j<n;j++){
                if(i==j) qwe.push_back(0);
                else qwe.push_back(asd[i][j]);
            }
            answer.push_back(qwe);
        }
	}else if(!band){
        memset(asd,0,sizeof(asd));
        for(int i=0;i<n;i++){
            if(i==Find(i)) continue;
            asd[i][Find(i)]=asd[Find(i)][i]=1;
        }
        for(int i=0;i<n;i++){
            vector <int> qwe;
            for(int j=0;j<n;j++){
                qwe.push_back(asd[i][j]);
            }
            answer.push_back(qwe);
        }
	}else if(!BAND){
        vector <int> grafo[1000];
        for(int i=0;i<n;i++){
            grafo[Find(i)].push_back(i);
        }
        bool flag=false;
        for(int i=0;i<n;i++){
            if(grafo[i].empty()) continue;
            int v=grafo[i].size();
            if(v==2) return 0;
            for(int j=0;j<v;j++) asd[grafo[i][(j-1+v)%v]][grafo[i][j]]=asd[grafo[i][j]][grafo[i][(j-1+v)%v]]=1;
        }
        for(int i=0;i<n;i++){
            vector <int> qwe;
            for(int j=0;j<n;j++){
                if(i==j) qwe.push_back(0);
                else qwe.push_back(asd[i][j]);
            }
            answer.push_back(qwe);
        }
	}else{
        for(int i=0;i<=n;i++) ded[i]=i;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(p[i][j]==1){
                    Union1(i,j);
                }
            }
        }
        vector <int> grafo[1000];
        for(int i=0;i<n;i++){
            grafo[Find1(i)].push_back(i);
        }
        for(int i=0;i<n;i++){
            if(grafo[i].empty()) continue;
            int v=grafo[i].size();
            for(int j=0;j<v;j++) asd[i][grafo[i][j]]=asd[grafo[i][j]][i]=1;
        }
        vector <int> qwe;
        for(int i=0;i<n;i++){
            if(grafo[i].empty()) continue;
            qwe.push_back(i);
        }
        for(int i=0;i<n;i++) grafo[i].clear();
        for(auto i:qwe) grafo[Find(i)].push_back(i);
        for(int i=0;i<n;i++){
            if(grafo[i].empty()) continue;
            int v=grafo[i].size();
            if(v==2) return 0;
            for(int j=0;j<v;j++) asd[grafo[i][(j-1+v)%v]][grafo[i][j]]=asd[grafo[i][j]][grafo[i][(j-1+v)%v]]=1;
        }
        for(int i=0;i<n;i++){
            vector <int> qwe;
            for(int j=0;j<n;j++){
                if(i==j) qwe.push_back(0);
                else qwe.push_back(asd[i][j]);
            }
            answer.push_back(qwe);
        }
	}
	build(answer);
	return 1;
}



//#include "supertrees.h"
//#include <vector>
//
//int construct(std::vector<std::vector<int>> p) {
//	int n = p.size();
//	std::vector<std::vector<int>> answer;
//	for (int i = 0; i < n; i++) {
//		std::vector<int> row;
//		row.resize(n);
//		answer.push_back(row);
//	}
//	build(answer);
//	return 1;
//}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int j=0;j<p[i].size();j++){
      |                     ~^~~~~~~~~~~~
supertrees.cpp:131:14: warning: unused variable 'flag' [-Wunused-variable]
  131 |         bool flag=false;
      |              ^~~~

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