Submission #782061

#	Time	Username	Problem	Language	Result	Execution time	Memory
782061		bane	슈퍼트리 잇기 (IOI20_supertrees)	C++17	21 / 100	184 ms	22440 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;
	}
};



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


	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){
				adj[A][B] = adj[B][A] = 1;
			}
		}
	}

	for (int i = 0; i < n; i++){
		for (int j = i + 1; j < n; j++){
			if (adj[i][j]){
				DSU.Unite(i,j);
			}
		}
	}

	//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: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4