제출 #1162352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162352		Alfraganus	Connecting Supertrees (IOI20_supertrees)	C++20	0 / 100	0 ms	324 KiB

supertrees

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

using namespace std;

#define print(a) for(auto x : a) cout << x << ' '; cout << endl;

struct DSU {

	int size = 1;
	vector<int> par, sz;

	DSU (int n){
		par.resize(n);
		sz.resize(n);
		for(int i = 0; i < n; i ++)
			par[i] = i, sz[i] = 1;
	}

	void merge(int a, int b){
		a = find(a);
		b = find(b);

		if(a == b)
			return;
		
		if(sz[a] < sz[b])
			swap(a, b);

		par[b] = a;
		sz[a] += sz[b];
	}

	int find(int n){
		if(par[n] != n)
			return par[n] = find(par[n]);
		return par[n];
	}

};

int construct(vector<vector<int>> p) {
	int n = (int)p.size();
	DSU d(n);
	vector<vector<int>> ans(n, vector<int> (n));
	vector<bool> used(n + 1);
	for(int i = 0; i < n; i ++){
		if(used[i])
			continue;
		vector<int> cycle;
		cycle.push_back(i);
		bool flag = 1;
		for(int j = 0; j < n; j ++){
			if(p[i][j] == 2){
				if(used[j])
					flag = 0;
				else
					cycle.push_back(j);
			}
		}
		for(int j = 1; j < (int)cycle.size(); j ++){
			int x = cycle[j], cnt = 0;
			for(int j = 0; j < n; j ++)
				if(p[x][j] == 2)
					cnt ++;
			if(cnt != (int)cycle.size()){
				flag = 0;
				break;
			}
			for(auto y : cycle){
				if(x != y and p[x][y] != 2){
					flag = 0;
					break;
				}
			}
			if(!flag)
				break;
		}
		if(flag){
			for(int i = 1; i <= (int)cycle.size(); i ++){
				ans[cycle[i - 1]][cycle[i % (int)cycle.size()]] = 1;
				ans[cycle[i % (int)cycle.size()]][cycle[i - 1]] = 1;
				d.merge(cycle[i - 1], cycle[i % (int)cycle.size()]);
				used[cycle[i % (int)cycle.size()]] = 1;
			}
		}
	}
	for(int i = 0; i < n; i ++){
		for(int j = 0; j < n; j ++){
			if(p[i][j] == 0 and d.find(i) == d.find(j))
				return 0;
			if(p[i][j] == 1 and d.find(i) != d.find(j)){
				d.merge(i, j);
				ans[i][j] = 1;
				ans[j][i] = 1;
			}
		}
	}
	build(ans);
	return 1;
}

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