Submission #422435

#	Time	Username	Problem	Language	Result	Execution time	Memory
422435		Apiram	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	296 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
void markall(int i ,int j ,vector<int>&f,vector<int>&b,vector<vector<int>>&p,vector<vector<int>>&answer){
int k = b[i];
while(k!=-1){
int u = j;	
while(u!=-1){
if (!answer[k][u]){
p[k][u]--;
p[u][k]--;
answer[k][u]++;
answer[u][k]++;}
u=f[u];}
k=b[k];
}
}
bool check(vector<int>f,vector<int>b,int i ,int j,vector<vector<int>>p){
int k = b[i];
while(k!=-1){
int u = j;	
while(u!=-1){
if (p[k][u]<=0)return false;
u=f[u];}
k=b[k];
}
return true;
}
int construct(vector<std::vector<int>> p) {
	int n = p.size();
	vector<vector<int>>answer(n,vector<int>(n,0));
	vector<vector<int>>vanswer(n,vector<int>(n,0));
	for (int i =0;i<n;++i){
	p[i][i]=0;
	}
	for (int i =0;i<n;++i){
		for (int j =0;j<i;++j){
		if (p[i][j]>=3)return 0;
		}
	}
	vector<int>f(n,-1),b(n,-1);
	for (int i =0;i<n;++i){
		for (int j =0;j<n;++j){
		 if (p[i][j]>0){
		   if (check(f,b,i,j,p)){
		   f[i]=j;
		   b[j]=i;
		   answer[i][j]++;
		   answer[j][i]++;}
		   markall(i,j,f,b,p,vanswer);  
		 }
	}}
	for (int i =0;i<n;++i){
		for (int j =0;j<n;++j){
		if (p[i][j]>0)return 0;
		}
	}	
																							
	
	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