| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 36629 |
2017-12-13T01:15:03 Z |
imaxblue |
Park (BOI16_park) |
C++14 |
|
2500 ms |
51320 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()
int n, k, w, h, N, o, R,
x[2005], y[2005], r[2005], d[2005][4];
int ans[4][4], D;
pq<pii> q;
int dis(int X, int Y){
return int(sqrt(1LL*(x[X]-x[Y])*(x[X]-x[Y])+
0.0000001+1LL*(y[X]-y[Y])*(y[X]-y[Y])))-r[X]-r[Y];
}
void dijk(int O){
while(!q.empty()) q.pop();
fox(l, n){
q.push(mp(-d[l][O], l));
d[l][O]=(1 << 30);
}
while(!q.empty()){
D=-q.top().x; N=q.top().y; q.pop();
if (D>=d[N][O]) continue;
//cout << "*"<<N << ' ' << D << ' ' << O<< endl;
d[N][O]=D;
fox(l, n){
if (l==N) continue;
q.push(mp(-max(D, dis(N, l)), l));
}
}
}
int main(){
flood(d); flood(ans);
scanf("%i%i%i%i", &n, &k, &w, &h);
fox(l, n){
scanf("%i%i%i", &x[l], &y[l], &r[l]);
d[l][0]=x[l]-r[l];
d[l][1]=y[l]-r[l];
d[l][2]=w-x[l]-r[l];
d[l][3]=h-y[l]-r[l];
}
fox(l, 4) dijk(l);
fox(l, n){
fox(l2, 4){
fox(l4, 4)
if (l4!=l2) ans[l2][l4]=ans[l4][l2]=min(ans[l2][l4], max(d[l][l2], d[l][l2+1]));
}
fox(l3, 3){
ans[l3][3]=ans[3][l3]=min(ans[3][l3], max(d[l][0], d[l][3]));
}
ans[0][3]=ans[3][0]=min(ans[0][3], max(d[l][0], d[l][2]));
ans[1][2]=ans[1][2]=min(ans[1][2], max(d[l][0], d[l][2]));
ans[0][1]=ans[1][0]=min(ans[1][0], max(d[l][1], d[l][3]));
ans[2][3]=ans[3][2]=min(ans[2][3], max(d[l][1], d[l][3]));
}
/*fox(l, n){
fox(l2, n) printf("%i ", ans[l][l2]);
printf("\n");
}*/
fox(l, k){
scanf("%i%i", &R, &o);
--o;
R*=2;
fox(l, 4){
if (R<=ans[o][l]) printf("%i", l+1);
}
printf("\n");
}
return 0;
}
/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/
Compilation message
park.cpp: In function 'int main()':
park.cpp:73:70: warning: operation on 'ans[1][2]' may be undefined [-Wsequence-point]
ans[1][2]=ans[1][2]=min(ans[1][2], max(d[l][0], d[l][2]));
^
park.cpp:54:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i%i%i%i", &n, &k, &w, &h);
^
park.cpp:56:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i%i%i", &x[l], &y[l], &r[l]);
^
park.cpp:82:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i%i", &R, &o);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2500 ms |
51320 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
2936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2500 ms |
51320 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
