Submission #619779

#	Time	Username	Problem	Language	Result	Execution time	Memory
619779		KLPP	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	185 ms	24060 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long int lld;
#define trav(a,v) for(auto a:v)

class DSU{
	int sz[1000000];
	int parent[1000000];
	int n;
	public:
	void init(int N){
		n=N;
		rep(i,0,n)sz[i]=1,parent[i]=i;
	}
	int root(int x){
		if(x==parent[x])return x;
		parent[x]=root(parent[x]);
		return parent[x];
	}
	void merge(int a, int b){
		a=root(a);
		b=root(b);
		if(a==b)return;
		if(sz[a]<sz[b])swap(a,b);
		sz[a]+=sz[b];
		parent[b]=a;
	}
};
DSU D;
DSU D2;
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);
	}
	
	D.init(n);
	rep(i,0,n){
		rep(j,0,n){
			if(p[i][j]==1)D.merge(i,j);
		}
	}
	rep(i,0,n){
		bool B=true;
		rep(j,i+1,n){
			if(D.root(j)==D.root(i)){
				B=false;
				if(p[i][j]!=1){
					return 0;
				}
			}
		}
		if(B){
			rep(j,0,i){
				if(D.root(j)==D.root(i))answer[i][j]=1,answer[j][i]=1;
			}
		}
	}
	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