Submission #993215

#	Time	Username	Problem	Language	Result	Execution time	Memory
993215		Newtonabc	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	348 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int pa[N];
bool cy[N][N];
set<int> s;
int root(int x){
	if(pa[x]==x) return x;
	else return pa[x]=root(pa[x]);
}
int construct(vector<vector<int> > p) {
	int n = p.size();
	vector<vector<int> > answer;
	for (int i = 0; i < n; i++) {
		vector<int> row(n,0);
		answer.push_back(row);
	}
	for(int i=0;i<n;i++) pa[i]=i;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(p[i][j]==1 && root(i)!=root(j)){
				answer[i][j]=1;
				answer[j][i]=1;
				pa[root(i)]=root(j);
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			int a,b;
			if(p[i][j]==2){
				a=root(i),b=root(j);
				s.insert(a);
				s.insert(b);
			}
		}
	}
	int prev=*s.begin(),first=*s.begin();
	for(set<int>::iterator it=s.begin();it!=s.end();it++){
		if(it==s.begin()) continue;
		answer[*it][prev]=1;
		answer[prev][*it]=1;
		prev=*it;
	}
	answer[first][*s.end()]=1;
	answer[*s.end()][first]=1;
	build(answer);
	return 1;
}

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