Submission #302518

#	Time	Username	Problem	Language	Result	Execution time	Memory
302518		FlowerOfSorrow	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	285 ms	22264 KiB

supertrees

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

int construct(vector<vector<int>> p){
	int n = (int)p.size();
	vector<int> vis1(n), vis2(n);
	vector<vector<int>> adjm(n, vector<int>(n));
	for(auto u = 0; u < n; ++ u){
		for(auto v = 0; v < n; ++ v){
			if(p[u][v] == 3){
				return 0;
			}
		}
	}
	auto link = [&](int u, int v){
		adjm[u][v] = adjm[v][u] = true;
	};
	for(auto u = 0; u < n; ++ u){
		if(!vis1[u]){
			vector<int> cur;
			function<void(int)> dfs_connected = [&](int u){
				vis1[u] = true;
				cur.push_back(u);
				for(auto v = 0; v < n; ++ v){
					if(!vis1[v] && p[u][v]){
						dfs_connected(v);
					}
				}
			};
			dfs_connected(u);
			for(auto u: cur){
				for(auto v: cur){
					if(!p[u][v]){
						return 0;
					}
				}
			}
			vector<vector<int>> groups;
			for(auto u: cur){
				if(!vis2[u]){
					groups.emplace_back();
					auto &g = groups.back();
					function<void(int)> dfs_spike = [&](int u){
						vis2[u] = true;
						g.push_back(u);
						for(auto v = 0; v < n; ++ v){
							if(!vis2[v] && p[u][v] == 1){
								dfs_spike(v);
							}
						}
					};
					dfs_spike(u);
					for(auto u: g){
						for(auto v: g){
							if(p[u][v] ^ 1){
								return 0;
							}
						}
					}
				}
			}
			if((int)groups.size() == 2){
				return 0;
			}
			for(auto &g: groups){
				for(auto i = 1; i < (int)g.size(); ++ i){
					link(g[i - 1], g[i]);
				}
			}
			for(auto i = 1; i < (int)groups.size(); ++ i){
				link(groups[i - 1][0], groups[i][0]);
			}
			if((int)groups.size() ^ 1){
				link(groups[(int)groups.size() - 1][0], groups[0][0]);
			}
		}
	}
	build(adjm);
	return 1;
}

/*

*/

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

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