Submission #782122

#	Time	Username	Problem	Language	Result	Execution time	Memory
782122		bane	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	209 ms	28132 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"

using namespace std;

struct DisjointSetUnion{
	int N;
	vector<int>sz;
	vector<int>link;
	DisjointSetUnion(int n): N(n){
		sz.resize(n);
		link.resize(n);
		for (int i = 0; i < n; i++){
			link[i] = i;
			sz[i] = 1;
		}
	}

	int Find(int a){
		if (a == link[a])return a;
		return link[a] = Find(link[a]);
	}

	bool Unite(int a, int b){
		a = Find(a), b = Find(b);
		if (a == b)return false;
		if (sz[a] < sz[b])swap(a,b);
		sz[a] += sz[b];
		link[b] = a;
		return true;
	}
};


class Uniderected_Graph{
	public:
		int N, mx = 0, far = 0;
		vector<vector<int>>adj;
		vector<int>Visited;
		Uniderected_Graph(int _N) : N(_N){
			adj.resize(N);
			Visited.resize(N);
			Visited.assign(N,0);
		}

		void Add_Edge(int A, int B){
			adj[A].push_back(B);
			adj[B].push_back(A);
		}

		void Far(int u, int p, int depth = 0){
			if (depth > mx){
				mx = depth;
				far = u;
			}
			Visited[u] = 1;
			for (int& nxt : adj[u]){
				if (nxt == p)continue;
				Far(nxt, u, depth + 1);
			}
		}

		pair<int,int> Find_Diameter(int Source){
			mx = -1, far = 0;
			Far(Source,Source,0);
			int A = far;
			mx = -1, far = 0;
			Far(A,A,0);
			int B = far;
			return make_pair(A,B);
		}

		void Dfs(int u,vector<int>& p){
			if (Visited[u])return;
			Visited[u] = 1;
			p.push_back(u);
			for (int& nxt : adj[u]){
				Dfs(nxt, p);
			}
		}

		vector<int>pracka(int Source){
			vector<int>ans;
			Dfs(Source,ans);
			return ans;
		}
};



int construct(vector<vector<int>> p) {
	int n = (int)p.size();
	vector<vector<int>>adj(n,vector<int>(n));
	DisjointSetUnion DSU(n + 1);
	for (int i = 0; i < n; i++){
		for (int j = i + 1; j < n; j++){
			if (p[i][j] == 3)return 0;
			if (p[i][j] == 1){
				DSU.Unite(i,j);
			}
		}
	}

	//check if all p[i][j] = 1 in trees, otherwise contradiction
	for (int i = 0; i < n; i++){
		for (int j = i + 1; j < n; j++){
			int A = DSU.Find(i) , B = DSU.Find(j);
			if (p[i][j] != 1 && A == B){
				return 0;
			}
			if (A != i){
				adj[A][i] = adj[i][A] = 1;
			}
			if (B!=j){
				adj[B][j] = adj[j][B] = 1;
			}
		}
	}


	//All good

	//merge trees in cycle
	Uniderected_Graph G(n+1);

	for (int i = 0; i < n; i++){
		for (int j = i + 1; j < n; j++){
			int A = DSU.Find(i), B = DSU.Find(j);
			if (A == B)continue;
			//Different component
			if (p[A][B] == 2){
				G.Add_Edge(A,B);
			}
		}
	}


	for (int i = 0; i < n; i++){
		if (G.Visited[i])continue;
		auto response = G.pracka(i);
		if (response.size() == 1)continue;
		if (response.size() == 2)return 0;
		adj[response[0]][response.back()] = 1;
		adj[response.back()][response[0]] = 1;
		DSU.Unite(response.back(), response[0]);
		for (int j = 1; j < (int)response.size(); j++){

			adj[response[j]][response[j-1]] = 1;
			adj[response[j-1]][response[j]] = 1;
			DSU.Unite(response[j],response[j-1]);
		}
	}

	//check if trees merged in cycle and have p[i][j] = 0, should be in another component
	//check if all needed are in same component
	for (int i = 0; i < n; i++){
		for (int j = i + 1; j < n; j++){
			int A = DSU.Find(i) , B = DSU.Find(j);
			if (p[i][j] == 0 && A == B)return 0;
			if (p[i][j] != 0 && A != B)return 0;
		}
	}

	build(adj);
	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