| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 258541 |
2020-08-06T05:57:20 Z |
송준혁(#5060) |
Park (BOI16_park) |
C++17 |
|
2500 ms |
760 KB |
#include <bits/stdc++.h>
#define pb push_back
#define lb lower_bound
#define fi first
#define se second
#define mup(a,x) a=min(a,x)
#define Mup(a,x) a=max(a,x)
#define INF 1234567890
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int N, Q, W, H;
int P[2020];
bool chk[2020];
LL X[2020], Y[2020], R[2020], A[6];
int rt(int u){
if (P[u] == u) return u;
return P[u] = rt(P[u]);
}
int main(){
scanf("%d %d", &N, &Q);
scanf("%d %d", &W, &H);
for (int i=1; i<=N; i++) scanf("%lld %lld %lld", &X[i], &Y[i], &R[i]);
LL lo=0, hi=1'000'000'000;
while (lo<=hi){
LL m=lo+hi>>1;
for (int i=1; i<=N; i++) P[i] = i;
for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
if ((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j])<((__int128)m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
P[rt(i)] = rt(j);
}
}
bool tf=false;
memset(chk, false, sizeof chk);
for (int i=1; i<=N; i++) if (X[i]-R[i]-m-m < 0) chk[rt(i)] = true;
for (int i=1; i<=N; i++) if (Y[i]-R[i]-m-m < 0 && chk[rt(i)]) {tf = true; break;}
if (tf) A[0]=m, hi=m-1;
else lo=m+1;
}
lo=0, hi=1'000'000'000;
while (lo<=hi){
LL m=lo+hi>>1;
for (int i=1; i<=N; i++) P[i] = i;
for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
if ((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j])<((__int128)m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
P[rt(i)] = rt(j);
}
}
bool tf=false;
memset(chk, false, sizeof chk);
for (int i=1; i<=N; i++) if (X[i]+R[i]+m+m > W) chk[rt(i)] = true;
for (int i=1; i<=N; i++) if (Y[i]-R[i]-m-m < 0 && chk[rt(i)]) {tf = true; break;}
if (tf) A[1]=m, hi=m-1;
else lo=m+1;
}
lo=0, hi=1'000'000'007;
while (lo<=hi){
LL m=lo+hi>>1;
for (int i=1; i<=N; i++) P[i] = i;
for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
if ((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j])<((__int128)m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
P[rt(i)] = rt(j);
}
}
bool tf=false;
memset(chk, false, sizeof chk);
for (int i=1; i<=N; i++) if (X[i]+R[i]+m+m > W) chk[rt(i)] = true;
for (int i=1; i<=N; i++) if (Y[i]+R[i]+m+m > H && chk[rt(i)]) {tf = true; break;}
if (tf) A[2]=m, hi=m-1;
else lo=m+1;
}
lo=0, hi=1'000'000'007;
while (lo<=hi){
LL m=lo+hi>>1;
for (int i=1; i<=N; i++) P[i] = i;
for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
if ((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j])<((__int128)m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
P[rt(i)] = rt(j);
}
}
bool tf=false;
memset(chk, false, sizeof chk);
for (int i=1; i<=N; i++) if (X[i]-R[i]-m-m < 0) chk[rt(i)] = true;
for (int i=1; i<=N; i++) if (Y[i]+R[i]+m+m > H && chk[rt(i)]) {tf = true; break;}
if (tf) A[3]=m, hi=m-1;
else lo=m+1;
}
lo=0, hi=1'000'000'007;
while (lo<=hi){
LL m=lo+hi>>1;
for (int i=1; i<=N; i++) P[i] = i;
for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
if ((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j])<((__int128)m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
P[rt(i)] = rt(j);
}
}
bool tf=false;
memset(chk, false, sizeof chk);
for (int i=1; i<=N; i++) if (X[i]-R[i]-m-m < 0) chk[rt(i)] = true;
for (int i=1; i<=N; i++) if (X[i]+R[i]+m+m > W && chk[rt(i)]) {tf = true; break;}
if (tf) A[4]=m, hi=m-1;
else lo=m+1;
}
lo=0, hi=1'000'000'007;
while (lo<=hi){
LL m=lo+hi>>1;
for (int i=1; i<=N; i++) P[i] = i;
for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++) {
if ((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j])<((__int128)m+m+R[i]+R[j])*(m+m+R[i]+R[j])){
P[rt(i)] = rt(j);
}
}
bool tf=false;
memset(chk, false, sizeof chk);
for (int i=1; i<=N; i++) if (Y[i]-R[i]-m-m < 0) chk[rt(i)] = true;
for (int i=1; i<=N; i++) if (Y[i]+R[i]+m+m > H && chk[rt(i)]) {tf = true; break;}
if (tf) A[5]=m, hi=m-1;
else lo=m+1;
}
while (Q--){
int x, y;
scanf("%d %d", &x, &y);
if (y == 1){
printf("1");
if (x < A[0] && x < A[1] && x < A[5]) printf("2");
if (x < A[0] && x < A[2] && x < A[4] && x < A[5]) printf("3");
if (x < A[0] && x < A[3] && x < A[4]) printf("4");
}
if (y == 2){
if (x < A[0] && x < A[1] && x < A[5]) printf("1");
printf("2");
if (x < A[1] && x < A[2] && x < A[4]) printf("3");
if (x < A[1] && x < A[3] && x < A[4] && x < A[5]) printf("4");
}
if (y == 3){
if (x < A[2] && x < A[0] && x < A[5] && x < A[4]) printf("1");
if (x < A[1] && x < A[2] && x < A[4]) printf("2");
printf("3");
if (x < A[2] && x < A[3] && x < A[5]) printf("4");
}
if (y == 4){
if (x < A[0] && x < A[3] && x < A[4]) printf("1");
if (x < A[1] && x < A[3] && x < A[4] && x < A[5]) printf("2");
if (x < A[2] && x < A[3] && x < A[5]) printf("3");
printf("4");
}
printf("\n");
}
return 0;
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:29:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
LL m=lo+hi>>1;
~~^~~
park.cpp:46:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
LL m=lo+hi>>1;
~~^~~
park.cpp:63:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
LL m=lo+hi>>1;
~~^~~
park.cpp:80:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
LL m=lo+hi>>1;
~~^~~
park.cpp:97:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
LL m=lo+hi>>1;
~~^~~
park.cpp:114:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
LL m=lo+hi>>1;
~~^~~
park.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &Q);
~~~~~^~~~~~~~~~~~~~~~~
park.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &W, &H);
~~~~~^~~~~~~~~~~~~~~~~
park.cpp:26:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i=1; i<=N; i++) scanf("%lld %lld %lld", &X[i], &Y[i], &R[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1751 ms |
504 KB |
Output is correct |
| 2 |
Correct |
1734 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1758 ms |
444 KB |
Output is correct |
| 4 |
Correct |
1750 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1827 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1742 ms |
384 KB |
Output is correct |
| 7 |
Execution timed out |
2599 ms |
384 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
760 KB |
Output is correct |
| 2 |
Correct |
58 ms |
632 KB |
Output is correct |
| 3 |
Correct |
59 ms |
632 KB |
Output is correct |
| 4 |
Correct |
59 ms |
632 KB |
Output is correct |
| 5 |
Correct |
60 ms |
760 KB |
Output is correct |
| 6 |
Correct |
74 ms |
760 KB |
Output is correct |
| 7 |
Correct |
39 ms |
632 KB |
Output is correct |
| 8 |
Correct |
39 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1751 ms |
504 KB |
Output is correct |
| 2 |
Correct |
1734 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1758 ms |
444 KB |
Output is correct |
| 4 |
Correct |
1750 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1827 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1742 ms |
384 KB |
Output is correct |
| 7 |
Execution timed out |
2599 ms |
384 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
