Submission #576794

#	Time	Username	Problem	Language	Result	Execution time	Memory
576794		1ne	슈퍼트리 잇기 (IOI20_supertrees)	C++14	Compilation error	0 ms	0 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
struct DSU{
	vector<int>parent;
	vector<int>sz;
	vector<vector<int>>comp;
	void build(int n){
		parent.resize(n);
		sz.resize(n);
		comp.resize(n);
		for (int i = 0;i<n;++i){
			parent[i] = i;
			sz[i] = 1;
			comp[i].push_back(i);
		}
	}
	int findsets(int v){
		if (v == parent[v])return v;
		parent[v] = findsets(parent[v]);
		return parent[v];
	}
	bool unionset(int a,int b,vector<vector<int>>&p,vector<vector<int>>&answer,bool ok){
		int u = findsets(a);
		int v = findsets(b);
		if (sz[u] < sz[v])swap(u,v);
		set<pair<int,int>>brr;
		if (ok && u == v)return false;
		if (!ok){
			for (auto x:comp[v]){
				for (auto y:comp[u]){
					if (x == y)continue;
					if (brr.find({x,y})!=brr.end())continue;
					if (answer[x][y])continue;
					if (!p[x][y])return false;
						p[x][y]--;
						p[y][x]--;
						brr.insert({x,y});
						brr.insert({y,x});
				}
			}
		}
		bool got = false;
		for (auto x:comp[v]){
			for (auto y:comp[u]){
				if (!answer[x][y] && x != y){
					answer[x][y] = true;
					answer[y][x] = true;
					got = true;
					break;
				}
			}
			if (got)break;
		}
		if (ok){
			parent[v] = u;
			sz[u]+=sz[v];
			while(!comp[v].empty()){
				comp[u].push_back(comp[v].back());
				comp[v].pop_back();
			}
		}
		return true;
	};
};

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer(n,vector<int>(n,0));
	DSU st;
	st.build(n);
	for (int i = 0;i<n;++i){
		for (int j = i + 1;j<n;++j){
			if (p[i][j]){
				st.unionset(i,j,p,answer,1);
			}
		}
	}
	for (int i = 0;i<n;++i){
		for (int j = i + 1;j<n;++j){
			if (ans[i][j]){
				int u = findsets(i);
				int v = findsets(j);
				set<pair<int,int>>brr;
				for (auto x:st.comp[v]){
					for (auto y:st.comp[u]){
						if (x == y)continue;
						if (brr.find({x,y})!=brr.end())continue;
						if (!p[x][y])return 0;
							p[x][y]--;
							p[y][x]--;
							brr.insert({x,y});
							brr.insert({y,x});
					}
				}
			}
		}
	}
	for (int i = 0;i<n;++i){
		for (int j = i + 1;j<n;++j){
			if (p[i][j]){
				if (!st.unionset(i,j,p,answer,0)){
					return 0;
				}
			}
		}
	}
	for (int i = 0;i<n;++i){
		for (int j = 0;j < n;++j){
			if (i == j)continue;
			if (p[i][j])return 0;
		}
	}
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:87:8: error: 'ans' was not declared in this scope; did you mean 'abs'?
   87 |    if (ans[i][j]){
      |        ^~~
      |        abs
supertrees.cpp:88:13: error: 'findsets' was not declared in this scope
   88 |     int u = findsets(i);
      |             ^~~~~~~~