Submission #312375

#	Time	Username	Problem	Language	Result	Execution time	Memory
312375		huangqr	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	266 ms	22392 KiB

supertrees

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

int construct(std::vector<std::vector<int>> p) {
	using namespace std;
	int n = p.size();
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)if(p[i][j]==3||p[j][i]!=p[i][j])return 0;
	}
	int group[1005],ctr=-1;
	vector<set<int> >groups;
	for(int i=0;i<n;i++)group[i]=-1;
	for(int i=0;i<n;i++){
		if(p[i][i]!=1)return 0;
		vector<int>r=p[i];
		if(group[i]==-1){
			group[i]=++ctr;
			set<int>cgp={i};
			for(int j=0;j<n;j++){
				if(j==i)continue;
				if(r[j]){
					if(group[j]!=-1)return 0;
					group[j]=ctr;
					cgp.insert(j);
				}
			}
			groups.push_back(cgp);
		}
		else{
			int g=group[i];
			for(int j=0;j<n;j++){
				if(group[j]==g&&r[j]==0)return 0;
				if(group[j]!=g&&r[j])return 0;
			}
		}
	}
	ctr++;
//	for(auto x:groups){
//		for(auto y:x){
//			cout<<y<<" ";
//		}
//		cout<<"\n";
//	}
	
	
	
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		for(int j=0;j<n;j++)row.push_back(0);
		answer.push_back(row);
	}
	
	for(auto x:groups){
		auto y=x.begin(),yy=x.begin();
		y++;
		while(y!=x.end()){
			answer[*y][*yy]=answer[*yy][*y]=1;
			y++,yy++;
		}
	}
	
	build(answer);
	return 1;
}

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