Submission #1157194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157194		raczek	Izvanzemaljci (COI21_izvanzemaljci)	C++20	0 / 100	51 ms	3144 KiB

izvanzemaljci

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";}
auto operator <<(auto& o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X...) cerr<<"["#X"]: ", [](auto...$) {((cerr<<$<<"; "),...)<<endl;}(X)
#else 
#define debug(...){}
#endif
#define int long long
const int INF = 1e18+7;
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
#define eb emplace_back
vector<pair<int, int> > pts;
int check(int d, bool f = false)
{
	vector<vector<int> > graph(pts.size());
	for(auto& v : pts)
		for(auto& u : pts)
			if(u != v && max(abs(u.fi-v.fi), abs(u.se-v.se)) <= d)
				graph[&u-&(*pts.begin())].eb(&v-&(*pts.begin()));
	vector<int> depth(pts.size(), -1);
	int res = 0;
	int cnt = 0;
	vector<int> artpt(pts.size());
	function<int(int, int)> dfs = [&](int a, int de)
	{
		depth[a] = de;
		int lw = de;
		int chld = 0;
		for(auto v : graph[a])
			if(depth[v] == -1)
			{
				chld++;
				int l = dfs(v, de+1);
				if(artpt[v] != 0) chld--;
				if(l >= de && de != 0 && artpt[v] == 0)
					artpt[a] = graph[a].size(), cnt++;
				lw = min(lw, l);
			}
			else if(depth[a] - depth[v] > 1)
				lw = min(lw, depth[v]);
		if(de == 0 && chld >= 2)
			artpt[a] = graph[a].size(), cnt++;
		return lw;
	};
	for(int i=0;i<pts.size();i++)
		if(depth[i] == -1)
		{
			dfs(i, 0);
			res += cnt+1;
			cnt = 0;
		}
	if(f)
	{
		vector<bool> vis(pts.size());
		int x = INF, y = INF;
		function<void(int)> tr = [&](int a)
		{
			x = min(pts[a].fi, x);
			y = min(pts[a].se, y);
			vis[a] = true;
			for(auto v : graph[a])
				if(vis[v] == false && artpt[v] == 0)
					tr(v);
				else if(--artpt[v] == 0)
					vis[v] = true,
					x = min(pts[v].fi, x),
					y = min(pts[v].se, y);
		};
		for(int i=0;i<pts.size();i++)
		{
			if(vis[i] == false && artpt[i] == false)
			{
				x = y = INF;
				tr(i);
				cout<<x<<" "<<y<<" "<<d<<endl;
			}
		}
	}
	return res;
}
int32_t main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n, k;
	cin>>n>>k;
	pts.resize(n);
	for(auto& [x, y] : pts)
		cin>>x>>y;
	int p = 0, q = 1e9+7;
	while(p != q-1)
	{
		int pol = (p+q)/2;
		debug(p, q, pol, check(pol));
		if(check(pol) <= k)
			q = pol;
		else
			p = pol;
	}
	check(q, true);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 21
• Subtask 3: 0 / 12
• Subtask 4: 0 / 30
• Subtask 5: 0 / 32