답안 #50099 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50099	2018-06-07T14:11:17 Z	zetapi	원 고르기 (APIO18_circle_selection)	C++14	30 / 100	3000 ms	148360 KB

circle_selection

#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=4e5;
const int INF=1e12;
 
set<int> st;

map<int,int> maps;

vector< vector<pii> > vec(MAX);
 
int N,mnx,mny,ptr,X[MAX],Y[MAX],R[MAX],par[MAX],block[MAX][2];
 
bool ok(int F,int S)
{
	if((X[F]-X[S])*(X[F]-X[S])+(Y[F]-Y[S])*(Y[F]-Y[S])>(R[F]+R[S])*(R[F]+R[S]))
		return false;
	return true;
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
	/*cin.tie(0);
	cout.tie(0);*/
 	
 	/* 	input
 		11
		9 9 2
		13 2 1
		11 8 2
		3 3 2
		3 12 1
		12 14 1
		9 8 5
		2 8 2
		5 2 1
		14 4 2
		14 14 1
	*/
	priority_queue< pair<int,int> > qu;
 	mnx=INF;
 	mny=INF;
 	int k=-INF;
	cin>>N;
	for(int A=1;A<=N;A++)
	{
		cin>>X[A]>>Y[A]>>R[A];
		mnx=min(mnx,X[A]);
		mnx=min(mnx,Y[A]);
		k=max(k,R[A]);
		qu.push(mp(R[A],-A));
	}
	for(int A=1;A<=N;A++)
	{
		X[A]-=mnx;
		Y[A]-=mnx;
		block[A][0]=X[A]/k;
		block[A][1]=Y[A]/k;
		st.insert(block[A][1]);
	}
	for(auto A:st)
		maps[A]=++ptr;
	for(int A=1;A<=N;A++)
		vec[maps[block[A][1]]].pb(mp(block[A][0],A));
	//for(int A=1;A<=N;A++)
	while(!qu.empty())
	{
		int A=-qu.top().second;
		qu.pop();
		if(par[A])
			continue;
		par[A]=A;
		for(int B,C=block[A][1]-2;C<=block[A][1]+2;C++)
		{
			B=maps[C];
			if(vec[B].empty())
				continue;
			pii lol=mp(block[A][0]-2,0);
			for(vector<pii> itr it=vec[B].begin();it!=vec[B].end();it++)
			{
				if(par[it->second])
					continue;
				if(ok(A,it->second))
					par[it->second]=A;
			}
		}
	}
	for(int A=1;A<=N;A++)
		cout<<par[A]<<" ";
	return 0;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:87:8: warning: variable 'lol' set but not used [-Wunused-but-set-variable]
    pii lol=mp(block[A][0]-2,0);
        ^~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	9720 KB	Output is correct
2	Correct	10 ms	9828 KB	Output is correct
3	Correct	11 ms	9904 KB	Output is correct
4	Correct	10 ms	9980 KB	Output is correct
5	Correct	10 ms	9980 KB	Output is correct
6	Correct	12 ms	9980 KB	Output is correct
7	Correct	11 ms	9980 KB	Output is correct
8	Correct	10 ms	9980 KB	Output is correct
9	Correct	11 ms	9980 KB	Output is correct
10	Correct	11 ms	10016 KB	Output is correct
11	Correct	12 ms	10048 KB	Output is correct
12	Correct	11 ms	10048 KB	Output is correct
13	Correct	11 ms	10092 KB	Output is correct
14	Correct	10 ms	10096 KB	Output is correct
15	Correct	11 ms	10196 KB	Output is correct
16	Correct	10 ms	10196 KB	Output is correct
17	Correct	11 ms	10196 KB	Output is correct
18	Correct	12 ms	10196 KB	Output is correct
19	Correct	14 ms	10612 KB	Output is correct
20	Correct	14 ms	10620 KB	Output is correct
21	Correct	14 ms	10620 KB	Output is correct
22	Correct	32 ms	11916 KB	Output is correct
23	Correct	26 ms	12300 KB	Output is correct
24	Correct	24 ms	12300 KB	Output is correct
25	Correct	30 ms	12300 KB	Output is correct
26	Correct	27 ms	12300 KB	Output is correct

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	319 ms	38964 KB	Output is correct
2	Correct	298 ms	38964 KB	Output is correct
3	Correct	284 ms	39044 KB	Output is correct
4	Correct	277 ms	39044 KB	Output is correct
5	Execution timed out	3058 ms	39044 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	39044 KB	Output is correct
2	Correct	441 ms	39044 KB	Output is correct
3	Correct	1923 ms	40960 KB	Output is correct
4	Correct	1857 ms	40992 KB	Output is correct
5	Correct	2905 ms	40992 KB	Output is correct
6	Correct	727 ms	40992 KB	Output is correct
7	Correct	235 ms	40992 KB	Output is correct
8	Correct	54 ms	40992 KB	Output is correct
9	Correct	2705 ms	40992 KB	Output is correct
10	Execution timed out	3071 ms	40992 KB	Time limit exceeded

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1893 ms	51948 KB	Output is correct
2	Correct	2461 ms	148360 KB	Output is correct
3	Correct	1821 ms	148360 KB	Output is correct
4	Correct	2433 ms	148360 KB	Output is correct
5	Correct	2275 ms	148360 KB	Output is correct
6	Correct	639 ms	148360 KB	Output is correct

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	9720 KB	Output is correct
2	Correct	10 ms	9828 KB	Output is correct
3	Correct	11 ms	9904 KB	Output is correct
4	Correct	10 ms	9980 KB	Output is correct
5	Correct	10 ms	9980 KB	Output is correct
6	Correct	12 ms	9980 KB	Output is correct
7	Correct	11 ms	9980 KB	Output is correct
8	Correct	10 ms	9980 KB	Output is correct
9	Correct	11 ms	9980 KB	Output is correct
10	Correct	11 ms	10016 KB	Output is correct
11	Correct	12 ms	10048 KB	Output is correct
12	Correct	11 ms	10048 KB	Output is correct
13	Correct	11 ms	10092 KB	Output is correct
14	Correct	10 ms	10096 KB	Output is correct
15	Correct	11 ms	10196 KB	Output is correct
16	Correct	10 ms	10196 KB	Output is correct
17	Correct	11 ms	10196 KB	Output is correct
18	Correct	12 ms	10196 KB	Output is correct
19	Correct	14 ms	10612 KB	Output is correct
20	Correct	14 ms	10620 KB	Output is correct
21	Correct	14 ms	10620 KB	Output is correct
22	Correct	32 ms	11916 KB	Output is correct
23	Correct	26 ms	12300 KB	Output is correct
24	Correct	24 ms	12300 KB	Output is correct
25	Correct	30 ms	12300 KB	Output is correct
26	Correct	27 ms	12300 KB	Output is correct
27	Correct	24 ms	148360 KB	Output is correct
28	Correct	18 ms	148360 KB	Output is correct
29	Correct	19 ms	148360 KB	Output is correct
30	Correct	47 ms	148360 KB	Output is correct
31	Correct	37 ms	148360 KB	Output is correct
32	Correct	48 ms	148360 KB	Output is correct
33	Correct	112 ms	148360 KB	Output is correct
34	Correct	103 ms	148360 KB	Output is correct
35	Correct	153 ms	148360 KB	Output is correct
36	Correct	442 ms	148360 KB	Output is correct
37	Correct	529 ms	148360 KB	Output is correct
38	Correct	404 ms	148360 KB	Output is correct
39	Execution timed out	3060 ms	148360 KB	Time limit exceeded
40	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	9720 KB	Output is correct
2	Correct	10 ms	9828 KB	Output is correct
3	Correct	11 ms	9904 KB	Output is correct
4	Correct	10 ms	9980 KB	Output is correct
5	Correct	10 ms	9980 KB	Output is correct
6	Correct	12 ms	9980 KB	Output is correct
7	Correct	11 ms	9980 KB	Output is correct
8	Correct	10 ms	9980 KB	Output is correct
9	Correct	11 ms	9980 KB	Output is correct
10	Correct	11 ms	10016 KB	Output is correct
11	Correct	12 ms	10048 KB	Output is correct
12	Correct	11 ms	10048 KB	Output is correct
13	Correct	11 ms	10092 KB	Output is correct
14	Correct	10 ms	10096 KB	Output is correct
15	Correct	11 ms	10196 KB	Output is correct
16	Correct	10 ms	10196 KB	Output is correct
17	Correct	11 ms	10196 KB	Output is correct
18	Correct	12 ms	10196 KB	Output is correct
19	Correct	14 ms	10612 KB	Output is correct
20	Correct	14 ms	10620 KB	Output is correct
21	Correct	14 ms	10620 KB	Output is correct
22	Correct	32 ms	11916 KB	Output is correct
23	Correct	26 ms	12300 KB	Output is correct
24	Correct	24 ms	12300 KB	Output is correct
25	Correct	30 ms	12300 KB	Output is correct
26	Correct	27 ms	12300 KB	Output is correct
27	Correct	319 ms	38964 KB	Output is correct
28	Correct	298 ms	38964 KB	Output is correct
29	Correct	284 ms	39044 KB	Output is correct
30	Correct	277 ms	39044 KB	Output is correct
31	Execution timed out	3058 ms	39044 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

답안 #50099

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 0 / 12.0

Subtask #3 0 / 15.0

Subtask #4 23.0 / 23.0

Subtask #5 0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
0 / 12.0

Subtask #3
0 / 15.0

Subtask #4
23.0 / 23.0

Subtask #5
0 / 30.0

Subtask #6
0 / 13.0