Submission #782011

#	Time	Username	Problem	Language	Result	Execution time	Memory
782011		bane	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	188 ms	24140 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);
		}

		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);
		}
};



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){
				DSU.Unite(A,B);
				G.Add_Edge(A,B);
				adj[A][B] = adj[B][A] = 1;
			}
		}
	}

	int Visited[n+1];
	for (int i = 0; i < n; i++){
		Visited[i] = 0;
	}

	for (int i = 0; i < n; i++){
		if (G.Visited[i])continue;
		pair<int,int>Connect = G.Find_Diameter(i);
		if (Connect.first == Connect.second)continue;
		if (adj[Connect.first][Connect.second])return 0; // cycle of length 2
		adj[Connect.first][Connect.second] = 1;
		adj[Connect.second][Connect.first] = 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;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:123:6: warning: variable 'Visited' set but not used [-Wunused-but-set-variable]
  123 |  int Visited[n+1];
      |      ^~~~~~~

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