제출 #317855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
317855		tengiz05	슈퍼트리 잇기 (IOI20_supertrees)	C++17	19 / 100	272 ms	22268 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
	vector<int> p, rnk, sz;
	void init(int n){
		p.assign(n, 0);rnk.assign(n, 0);sz.assign(n, 1);
		for(int i=0;i<n;i++)p[i] = i;
	}
	int par(int i){
		if(p[i] == i)return i;
		else return p[i] = par(p[i]);
	}
	bool issame(int i, int j){
		return (par(i) == par(j));
	}
	void merge(int i, int j){
		i=par(i), j=par(j);
		if(i == j)return;
		if(rnk[i] > rnk[j]){
			rnk[i]++;sz[i] += sz[j];
			p[j] = i;
		}else {
			rnk[j]++;sz[j] += sz[i];
			p[i] = j;
		}
	}
	int setsize(int i){
		return sz[par(i)];
	}
};
int construct(vector<vector<int>> p) {
	int n = p.size();
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(p[i][j] == 3)return 0;
		}
	}
	DSU dsu; dsu.init(n);
	for(int i=0;i<n;i++){
		for(int j=0;j<i;j++){
			if(p[i][j] == 0 && dsu.issame(i, j))return 0;
			else if(p[i][j] > 0){
				dsu.merge(i, j);
			}
		}
	}
	vector<bool> used(n);
	vector<bool> ok(n, true);
	vector<vector<int>> ans(n, vector<int>(n,0));
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(i != j && p[i][j] == 1)ok[i] = false;
		}
	}
	DSU d; d.init(n);
	vector<int> par(n);
	for(int i=0;i<n;i++){
		for(int j=0;j<i;j++){
			if(p[i][j] == 1){
				if(d.issame(i, j))continue;
				par[j] = i;
				ans[i][j] = 1;
				ans[j][i] = 1;
				d.merge(i, j);
			}
		}par[i]=i;
		if(used[i])continue;
		int ind = -1;
		for(int j=i+1;j<n;j++){
			if(p[i][j] == 2 && !used[j])ind = j;
		}
		if(ind == -1 || !ok[i])continue;
		queue<int> q;q.push(i);used[i] = true;
		vector<int> t;
		while(!q.empty()){
			int u = q.front();q.pop();
			t.push_back(u);
			for(int v=0;v<n;v++){
				if(ok[v] && !used[v] && p[u][v] == 2){
					used[v] = true;
					par[v] = v;
					q.push(v);
				}
			}
		}//for(auto x : t)cout << x << ' ';cout << '\n';
		if(t.size() < 3)return 0;
		t.push_back(t[0]);
		for(int j=1;j<(int)t.size();j++){
			ans[t[j]][t[j-1]] = 1;
			ans[t[j-1]][t[j]] = 1;
		}
	}
/*	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cout << ans[i][j] << ' ';}cout << '\n';}*/
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(d.issame(i, j) && p[i][j] != 1)return 0;
			if(dsu.issame(i, j) && par[i] != par[j] && p[i][j] != 2)return 0;
		//	if(!dsu.issame(i, j) && p[i][j])return 0;
		}
	}
	build(ans);
	return 1;
}
/*

5
1 1 2 2 1
1 1 2 2 2
2 2 1 2 2
2 2 2 1 2
1 2 2 2 1

*/

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