oj.uz

Submission #64272

# Submission time Handle Problem Language Result Execution time Memory
64272 2018-08-03T21:34:16 Z zetapi Park (BOI16_park) C++14
0 / 100
 1207 ms 52960 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb  push_back
#define mp  make_pair
#define int long long
#define itr ::iterator 

typedef pair<int,int> pii;

const int MAX=1e5;
const int INF=1e9;

struct data
{
	int X;
	int Y;
	int R;
} 	Circle[MAX],People[MAX];

vector<pair<int,pii>> edges;

vector<int>	res[MAX];

int N,M,W,H,ptr,par[MAX],order[MAX];

int sq(int f)
{
	return f*f;
}

bool ok(int f,int s,int r)
{
	if(s>=N)
	{
		switch(s-N)
		{
			case 0: return Circle[f].Y-Circle[f].R-2*r>=0;;
			case 1: return Circle[f].X+Circle[f].R+2*r<=W;
			case 2: return Circle[f].Y+Circle[f].R+2*r<=H;
			case 3: return Circle[f].X-Circle[f].R-2*r>=0;
		}
	}
	return sq(Circle[f].X-Circle[s].X)+sq(Circle[f].Y-Circle[s].Y)>=sq(Circle[f].R+Circle[s].R+2*r);
}

int find(int f,int s)
{
	int low=0,high=INF,mid,res=0;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(ok(f,s,mid))
		{
			res=mid;
			low=mid+1;
		}
		else
			high=mid-1;
	}
	return res;
}

int root(int X)
{
	if(par[X]==X)
		return X;
	return par[X]=root(par[X]);
}

void unions(int X,int Y)
{
	int u=root(X),v=root(Y);
	par[u]=v;
	return ;
}

bool cmp(int f,int s)
{
	return People[f].R<People[s].R;
}

int pre(int X)
{
	return (X-1+4)%4;
}

int next(int X)
{
	return (X+1+4)%4;
}

signed main()
{
	ios_base::sync_with_stdio(false);

	cin>>N>>M;
	cin>>W>>H;
	for(int A=0;A<N;A++)
		cin>>Circle[A].X>>Circle[A].Y>>Circle[A].R;
	for(int A=0;A<M;A++)
	{
		cin>>People[A].R>>People[A].X;
		People[A].X--;
		order[A]=A;
	}
	for(int A=0;A<N;A++)
		for(int B=A+1;B<N+4;B++)
			edges.pb(mp(find(A,B),mp(A,B)));
	sort(edges.begin(),edges.end());
	//for(auto A:edges)
	//	cout<<A.first<<" "<<A.second.first<<" "<<A.second.second<<"\n";
	for(int A=0;A<N+4;A++)
		par[A]=A;
	int ptr=0;
	for(int A=0;A<M;A++)
	{
		//cout<<order[A]<<" ha ha\n";
		while(ptr<edges.size() and edges[ptr].first<People[order[A]].R)
		{
			//cout<<edges[ptr].second.first<<" edges  "<<edges[ptr].second.second<<" limit is "<<edges[ptr].first<<"\n";
			unions(edges[ptr].second.first,edges[ptr].second.second);
			++ptr;
		}
		//cout<<ptr<<"\n";
		int corner=People[order[A]].X;
		int previous=pre(corner);
		int f_0=corner;
		int f_1=next(f_0);
		int f_2=next(f_1);
		int f_3=next(f_2);
		corner+=N;
		previous+=N;
		f_0+=N;
		f_1+=N;
		f_2+=N;
		f_3+=N;
		//cout<<f_0<<" "<<f_1<<" "<<f_2<<" "<<f_3<<"\n";
		//cout<<root(f_0)<<" "<<root(f_1)<<" "<<root(f_2)<<" "<<root(f_3)<<"\n";
		if(root(previous)!=root(corner) and root(corner)!=root(f_1) and root(corner)!=root(f_1))
			res[order[A]].pb(f_1-N);
		if(root(previous)!=root(corner) and root(f_1)!=root(f_2) and root(previous)!=root(f_1))
			res[order[A]].pb(f_2-N);
		if(root(previous)!=root(corner) and root(f_2)!=root(f_3) and root(previous)!=root(f_1))
			res[order[A]].pb(f_3-N);
	}
	for(int A=0;A<M;A++)
	{
		res[A].pb(People[A].X);
		sort(res[A].begin(),res[A].end());
		for(auto B:res[A])
			cout<<B+1;
		cout<<"\n";
	}
	return 0;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:119:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr<edges.size() and edges[ptr].first<People[order[A]].R)
         ~~~^~~~~~~~~~~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1049 ms 52296 KB Output is correct
2 Correct 1075 ms 52440 KB Output is correct
3 Correct 1091 ms 52440 KB Output is correct
4 Correct 1177 ms 52716 KB Output is correct
5 Correct 1206 ms 52960 KB Output is correct
6 Correct 1079 ms 52960 KB Output is correct
7 Incorrect 1207 ms 52960 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

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

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1049 ms 52296 KB Output is correct
2 Correct 1075 ms 52440 KB Output is correct
3 Correct 1091 ms 52440 KB Output is correct
4 Correct 1177 ms 52716 KB Output is correct
5 Correct 1206 ms 52960 KB Output is correct
6 Correct 1079 ms 52960 KB Output is correct
7 Incorrect 1207 ms 52960 KB Output isn't correct
8 Halted 0 ms 0 KB -