oj.uz

Submission #982237

# Submission time Handle Problem Language Result Execution time Memory
982237 2024-05-14T04:18:04 Z Faisal_Saqib Circle selection (APIO18_circle_selection) C++17
7 / 100
 858 ms 342884 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e5+100;
const int SQ=20;//  333 444
vector<int> adj[N];
ll who[N];
void solve()
{
	ll n;
	cin>>n;
	vector<ll> x(n),y(n),r(n);
	for(int i=0;i<n;i++)
		cin>>x[i]>>y[i]>>r[i];
	if((n<=5000))
	{
		for(int i=0;i<n;i++)
			{
				for(int j=0;j<=i;j++)
				{
					// ( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ) <= (r1+r2)²
					ll dist=(r[i]+r[j])*(r[i]+r[j]);
					ll dp=( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
					if(dp<=dist)
					{
						adj[i].push_back(j);
						adj[j].push_back(i);
					}
				}
			}
			set<pair<int,int>> rem;
			for(int i=0;i<n;i++)
				rem.insert({-r[i],i});
			while(rem.size())
			{
				auto p=*begin(rem);
				rem.erase(begin(rem));
				if(who[p.second]!=0)
					continue;
				for(auto op:adj[p.second])
					if(who[op]==0)
						who[op]=p.second+1;
			}
			for(int i=0;i<n;i++)
			{
				cout<<who[i]<<' ';
			}
			cout<<'\n';
	}
	else
	{

		vector<pair<ll,ll>> tp(n);
		for(int i=0;i<n;i++)
		{
			tp[i].first=x[i];
			tp[i].second=i;
		}
		sort(begin(tp),end(tp));
		for(int jp=0;jp<n;jp++)
		{
			for(int l=-SQ;l<=SQ;l++)
			{
				if((jp+l)>=0 and (jp+l)<n)
				{
					int i=tp[jp].second;
					int j=tp[jp+l].second;
					ll dist=(r[i]+r[j])*(r[i]+r[j]);
					ll dp=( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
					if(dp<=dist)
					{
						adj[i].push_back(j);
						adj[j].push_back(i);
					}
				}
			}
		}
		for(int i=0;i<n;i++)
		{
			tp[i].first=y[i];
			tp[i].second=i;
		}
		sort(begin(tp),end(tp));
		for(int jp=0;jp<n;jp++)
		{
			for(int l=-SQ;l<=SQ;l++)
			{
				if((jp+l)>=0 and (jp+l)<n)
				{
					int i=tp[jp].second;
					int j=tp[jp+l].second;
					ll dist=(r[i]+r[j])*(r[i]+r[j]);
					ll dp=( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
					if(dp<=dist)
					{
						adj[i].push_back(j);
						adj[j].push_back(i);
					}
				}
			}
		}
		set<pair<int,int>> rem;
		for(int i=0;i<n;i++)
			rem.insert({-r[i],i});
		while(rem.size())
		{
			auto p=*begin(rem);
			rem.erase(begin(rem));
			if(who[p.second]!=0)
				continue;
			for(auto op:adj[p.second])
				if(who[op]==0)
					who[op]=p.second+1;
		}
		for(int i=0;i<n;i++)
		{
			cout<<who[i]<<' ';
		}
		cout<<'\n';
	}
}
int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	solve();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7512 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 3 ms 7516 KB Output is correct
16 Correct 9 ms 11712 KB Output is correct
17 Correct 8 ms 11356 KB Output is correct
18 Correct 7 ms 11612 KB Output is correct
19 Correct 212 ms 145116 KB Output is correct
20 Correct 187 ms 143320 KB Output is correct
21 Correct 166 ms 85052 KB Output is correct
22 Correct 27 ms 8028 KB Output is correct
23 Correct 27 ms 8028 KB Output is correct
24 Correct 27 ms 8140 KB Output is correct
25 Correct 27 ms 8016 KB Output is correct
26 Correct 27 ms 8024 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 858 ms 342884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Incorrect 125 ms 20520 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 46924 KB Output is correct
2 Correct 412 ms 47180 KB Output is correct
3 Incorrect 469 ms 52816 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7512 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 3 ms 7516 KB Output is correct
16 Correct 9 ms 11712 KB Output is correct
17 Correct 8 ms 11356 KB Output is correct
18 Correct 7 ms 11612 KB Output is correct
19 Correct 212 ms 145116 KB Output is correct
20 Correct 187 ms 143320 KB Output is correct
21 Correct 166 ms 85052 KB Output is correct
22 Correct 27 ms 8028 KB Output is correct
23 Correct 27 ms 8028 KB Output is correct
24 Correct 27 ms 8140 KB Output is correct
25 Correct 27 ms 8016 KB Output is correct
26 Correct 27 ms 8024 KB Output is correct
27 Incorrect 22 ms 17756 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7512 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 3 ms 7516 KB Output is correct
16 Correct 9 ms 11712 KB Output is correct
17 Correct 8 ms 11356 KB Output is correct
18 Correct 7 ms 11612 KB Output is correct
19 Correct 212 ms 145116 KB Output is correct
20 Correct 187 ms 143320 KB Output is correct
21 Correct 166 ms 85052 KB Output is correct
22 Correct 27 ms 8028 KB Output is correct
23 Correct 27 ms 8028 KB Output is correct
24 Correct 27 ms 8140 KB Output is correct
25 Correct 27 ms 8016 KB Output is correct
26 Correct 27 ms 8024 KB Output is correct
27 Incorrect 858 ms 342884 KB Output isn't correct
28 Halted 0 ms 0 KB -