Submission #302282

#	Time	Username	Problem	Language	Result	Execution time	Memory
302282		urd05	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	286 ms	22264 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
    int p[1000];
    void init() {
        memset(p,-1,sizeof(p));
    }
    int find(int a) {
        if (p[a]<0) {
            return a;
        }
        return p[a]=find(p[a]);
    }
    void merge(int a,int b) {
        a=find(a);
        b=find(b);
        if (a==b) {
            return;
        }
        p[b]=a;
    }
};

bool used[1000];

int construct(vector<vector<int>> v) {
	int n = v.size();
	vector<vector<int>> ret(n,vector<int>(n));
	UnionFind uf;
	uf.init();
	bool flag3=false;
	for (int i = 0; i < n; i++) {
	    for(int j=0;j<n;j++) {
	        if (v[i][j]!=0) {
	            uf.merge(i,j);
	            if (v[i][j]==3) {
	            	flag3=true;
				}
	        }
	    }
	}
	if (flag3) {
		if (n!=4) {
			return 0;
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if (i!=j&&v[i][j]!=3) {
					return 0;
				}
				if (i==j&&v[i][j]!=1) {
					return 0;
				}
			}
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if (i==j) {
					ret[i][j]=0;
				}
				ret[i][j]=1;
			}
		}
		ret[0][3]=0;
		ret[3][0]=0;
		build(ret);
		return 1;
	}
	for(int i=0;i<n;i++) {
	    for(int j=0;j<n;j++) {
	        if (v[i][j]!=0) {
	            if (uf.find(i)!=uf.find(j)) {
	                return 0;
	            }
	        }
	        else {
	            if (uf.find(i)==uf.find(j)) {
	                return 0;
	            }
	        }
	    }
	}
	for(int i=0;i<n;i++) {
	    if (!used[i]) {
	        vector<int> save;
	        save.push_back(i);
	        used[i]=true;
	        for(int j=i+1;j<n;j++) {
	            if (uf.find(j)==uf.find(i)) {
	                save.push_back(j);
	                used[j]=true;
	            }
	        }
	        UnionFind uf2;
	        uf2.init();
	        for(int j=0;j<save.size();j++) {
	            for(int k=0;k<save.size();k++) {
	                if (v[save[j]][save[k]]==1) {
	                    uf2.merge(save[j],save[k]);
	                }
	            }
	        }
	        for(int j=0;j<save.size();j++) {
	            for(int k=0;k<save.size();k++) {
	                if (v[save[j]][save[k]]!=1) {
	                    if (uf2.find(save[j])==uf2.find(save[k])) {
	                        return 0;
	                    }
	                }
	            }
	        }
	        bool used2[1000];
	        memset(used2,0,sizeof(used2));
	        vector<int> cycle;
	        for(int j=0;j<save.size();j++) {
	            if (!used2[save[j]]) {
	                used2[save[j]]=true;
	                cycle.push_back(save[j]);
	                for(int k=j+1;k<save.size();k++) {
	                    if (!used2[save[k]]&&uf2.find(save[j])==uf2.find(save[k])) {
	                        used2[save[k]]=true;
	                        ret[save[j]][save[k]]=1;
	                        ret[save[k]][save[j]]=1;
	                    }
	                }
	            }
	        }
	        if (cycle.size()==2) {
	            return 0;
	        }
	        if (cycle.size()==1) {
	            continue;
	        }
	        for(int j=0;j+1<cycle.size();j++) {
	            ret[cycle[j]][cycle[j+1]]=1;
	            ret[cycle[j+1]][cycle[j]]=1;
	        }
	        ret[cycle.back()][cycle[0]]=1;
	        ret[cycle[0]][cycle.back()]=1;
	    }
	}
	build(ret);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |          for(int j=0;j<save.size();j++) {
      |                      ~^~~~~~~~~~~~
supertrees.cpp:100:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |              for(int k=0;k<save.size();k++) {
      |                          ~^~~~~~~~~~~~
supertrees.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |          for(int j=0;j<save.size();j++) {
      |                      ~^~~~~~~~~~~~
supertrees.cpp:107:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |              for(int k=0;k<save.size();k++) {
      |                          ~^~~~~~~~~~~~
supertrees.cpp:118:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |          for(int j=0;j<save.size();j++) {
      |                      ~^~~~~~~~~~~~
supertrees.cpp:122:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |                  for(int k=j+1;k<save.size();k++) {
      |                                ~^~~~~~~~~~~~
supertrees.cpp:137:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |          for(int j=0;j+1<cycle.size();j++) {
      |                      ~~~^~~~~~~~~~~~~

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