Submission #406942

#	Time	Username	Problem	Language	Result	Execution time	Memory
406942		Dilshod_Imomov	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	249 ms	22212 KiB

supertrees

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

const int MAXN = 1e3 + 7;

vector < int > used, adj[MAXN];
vector < vector < int > > ans;

void dfs( int v ) {
	used[v] = 1;
	for ( auto u: adj[v] ) {
		ans[v][u] = 1;
		ans[u][v] = 1;
		if ( !used[u] ) {
			dfs( u );
		}
	}
}

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	vector < int > roots;
	used.assign(n, 0);
	ans.clear();
	for ( int i = 0; i < n; i++ ) {
		vector < int > vc(n);
		ans.push_back(vc);
	}
	for ( int i = 0; i < n; i++ ) {
		if ( used[i] ) {
			continue;
		}
		used[i] = 1;
		roots.push_back(i);
		cerr << i << ' ';
		for ( int j = 0; j < n; j++ ) {
			if ( i == j ) {
				if ( p[i][j] != 1 ) {
					cerr << "here1" << endl;
					return 0;
				}
				continue;
			}
			if ( p[i][j] == 3 ) {
				cerr << "here2" << endl;
				return 0;
			}
			if ( p[i][j] == 1 ) {
				adj[i].push_back(j);
				adj[j].push_back(i);
				used[j] = 1;
			}
		}
		vector < int > nb(n);
		for ( auto v: adj[i] ) {
			nb[v] = 1;
			for ( auto u: adj[i] ) {
				if ( p[v][u] != 1 ) {
					cerr << "here4" << endl;
					return 0;
				}
			}
		}
		nb[i] = 1;
		for ( auto v: adj[i] ) {
			for ( int j = 0; j < n; j++ ) {
				if ( !nb[j] && p[v][j] == 1 ) {
					return 0;
				}
			}
	}
	}
	cerr << endl;
	used.assign(n, 0);
	for ( auto i: roots ) {
		if ( used[i] ) {
			continue;
		}
		vector < int > cycle = { i };
		used[i] = 1;
		for ( auto j: roots ) {
			if ( p[i][j] == 2 ) {
				cycle.push_back(j);
			}
		}
		if ( cycle.size() == 2 ) {
			cerr << "here" << 5 << endl;
			return 0;
		}
		if ( cycle.size() == 1 ) {
			continue;
		}
		cerr << i << ' ';
		for ( int j = 1; j < (int)cycle.size(); j++ ) {
			adj[ cycle[j] ].push_back( cycle[j - 1] );
			adj[ cycle[j - 1] ].push_back( cycle[j] );
			used[cycle[j]] = 1;
			cerr << cycle[j] << " ";
		}
		cerr << endl;
		adj[ cycle.back() ].push_back(i);
		adj[i].push_back( cycle.back() );
		for ( auto v: cycle ) {
			for ( auto u: cycle ) {
				if ( v == u ) {
					continue;
				}
				if ( p[v][u] != 2 ) {
					return 0;
				}
				for ( auto x: adj[v] ) {
					for ( auto y: adj[u] ) {
						if ( used[x] || used[y] ) {
							continue;
						}
						if ( p[x][y] != 2 ) {
							cerr << "Here6" << endl;
							return 0;
						}
					}
					if ( !used[x] && p[x][u] != 2 ) {
						return 0;
					}
				}
			}
		}
	}
	used.assign(n, 0);
	for ( int i = 0; i < n; i++ ) {
		if ( !used[i] ) {
			dfs( i );
		}
	}
	build(ans);
	return  1;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
2
1 0
0 1
*/

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