Submission #825971

#	Time	Username	Problem	Language	Result	Execution time	Memory
825971		amunduzbaev	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	188 ms	24048 KiB

supertrees

#include "supertrees.h"

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

int construct(vector<vector<int>> p) {
	int n = p.size();
	
	vector<int> v;
	vector<int> used(n);
	function<void(int)> dfs = [&](int u){
		v.push_back(u);
		used[u] = 1;
		for(int x=0;x<n;x++){
			if(p[u][x] && !used[x]){
				dfs(x);
			}
		}
	};
	
	vector<vector<int>> ans(n, vector<int>(n, 0));
	
	for(int i=0;i<n;i++){
		if(used[i]) continue;
		dfs(i);
		
		for(auto x : v){
			for(auto y : v){
				if(!p[x][y]){
					return 0;
				}
				if(p[x][y] == 3){
					return 0;
				}
			}
		}
		
		vector<int> c(n), one;
		int last = 0;
		function<void(int)> dfs = [&](int u){
			one.push_back(u);
			c[u] = last;
			for(int x=0;x<n;x++){
				if(!c[x] && p[u][x] == 1){
					ans[u][x] = ans[x][u] = 1;
					dfs(x);
				}
			}
		};
		
		vector<int> cyc;
		for(auto u : v){
			if(c[u]) continue;
			last++;
			dfs(u);
			for(auto x : one){
				for(auto y : one){
					if(p[x][y] != 1) return 0;
				}
			}
			
			cyc.push_back(u);
			one.clear();
		}
		
		if((int)cyc.size() == 2) return 0;
		
		last = cyc.back();
		for(auto x : cyc){
			if(x != last) ans[x][last] = ans[last][x] = 1;
			last = x;
		}
		
		v.clear();
	}
	
	build(ans);
	
	return 1;
}

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