| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 46285 |
2018-04-18T18:35:59 Z |
ikura355 |
Park (BOI16_park) |
C++14 |
|
2500 ms |
35976 KB |
//aiming for 100 marks
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10;
const int maxq = 1e5 + 5;
const double eps = 1e-7;
struct point {
double x, y, r;
};
struct edge {
int x, y;
double dist;
edge(int _x = 0, int _y = 0, double _dist = 0) {
x = _x; y = _y; dist = _dist;
}
};
int n,m;
double w,h;
point p[maxn];
double fat[maxq];
int ent[maxq];
int ord[maxq];
vector<edge> hub;
int head[maxn];
int bad[10], con[10][10];
vector<int> ans[maxq];
double cut(point x, point y) {
return sqrt((x.x-y.x)*(x.x-y.x) + (x.y-y.y)*(x.y-y.y));
}
bool noey(double x, double y) {
return (y-x)>eps;
}
int findhead(int x) {
if(head[x]==x) return x;
return head[x] = findhead(head[x]);
}
bool cmp1(int x, int y) {
return fat[x] < fat[y];
}
bool cmp2(edge x, edge y) {
return x.dist < y.dist;
}
int main() {
scanf("%d%d%lf%lf",&n,&m,&w,&h);
for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r);
for(int tnum=1;tnum<=m;tnum++) scanf("%lf%d",&fat[tnum],&ent[tnum]), fat[tnum] *= 2.0;
//prep
for(int i=1;i<=m;i++) ord[i] = i;
sort(&ord[1],&ord[m+1],cmp1);
//tree - tree
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
hub.push_back(edge(i,j,cut(p[i],p[j])-p[i].r-p[j].r));
}
}
//tree - edge
for(int i=1;i<=n;i++) {
hub.push_back(edge(i,n+1,p[i].y-p[i].r));
hub.push_back(edge(i,n+2,w-p[i].x-p[i].r));
hub.push_back(edge(i,n+3,h-p[i].y-p[i].r));
hub.push_back(edge(i,n+4,p[i].x-p[i].r));
}
sort(hub.begin(),hub.end(),cmp2);
//solve
for(int i=1;i<=n+4;i++) head[i] = i;
for(int rep=1,cur=0;rep<=m;rep++) {
int tnum = ord[rep];
// printf("solve for %d\n",tnum);
cur = 0;
while(cur<hub.size() && noey(hub[cur].dist, fat[tnum])) {
// printf("\tadd edge %d %d\n",hub[cur].x,hub[cur].y);
head[findhead(hub[cur].x)] = findhead(hub[cur].y);
cur++;
}
//update connection
int id = 0;
for(int i=1;i<=4;i++) {
for(int j=i+1;j<=4;j++) {
bad[++id] = findhead(n+i)==findhead(n+j);
}
}
for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) con[i][j] = 1;
if(bad[1] || bad[2] || bad[3]) con[1][2] = con[2][1] = 0;
if(bad[2] || bad[3] || bad[4] || bad[5]) con[1][3] = con[3][1] = 0;
if(bad[3] || bad[5] || bad[6]) con[1][4] = con[4][1] = 0;
if(bad[1] || bad[4] || bad[5]) con[2][3] = con[3][2] = 0;
if(bad[1] || bad[2] || bad[5] || bad[6]) con[2][4] = con[4][2] = 0;
if(bad[2] || bad[4] || bad[6]) con[3][4] = con[4][3] = 0;
//show
// id = 0;
// for(int i=1;i<=4;i++) {
// for(int j=i+1;j<=4;j++) {
// printf("\t%d - %d : %d\n",i,j,bad[++id]);
// }
// }
//answer
for(int i=1;i<=4;i++) if(con[ent[tnum]][i]) ans[tnum].push_back(i);
}
for(int i=1;i<=m;i++) {
for(auto x : ans[i]) printf("%d",x);
printf("\n");
}
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(cur<hub.size() && noey(hub[cur].dist, fat[tnum])) {
~~~^~~~~~~~~~~
park.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lf%lf",&n,&m,&w,&h);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:49:29: 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("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:50:69: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int tnum=1;tnum<=m;tnum++) scanf("%lf%d",&fat[tnum],&ent[tnum]), fat[tnum] *= 2.0;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
425 ms |
35904 KB |
Output is correct |
| 2 |
Correct |
394 ms |
35904 KB |
Output is correct |
| 3 |
Correct |
395 ms |
35904 KB |
Output is correct |
| 4 |
Correct |
402 ms |
35976 KB |
Output is correct |
| 5 |
Correct |
413 ms |
35976 KB |
Output is correct |
| 6 |
Correct |
399 ms |
35976 KB |
Output is correct |
| 7 |
Correct |
378 ms |
35976 KB |
Output is correct |
| 8 |
Correct |
449 ms |
35976 KB |
Output is correct |
| 9 |
Correct |
3 ms |
35976 KB |
Output is correct |
| 10 |
Correct |
3 ms |
35976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
209 ms |
35976 KB |
Output is correct |
| 2 |
Correct |
223 ms |
35976 KB |
Output is correct |
| 3 |
Correct |
239 ms |
35976 KB |
Output is correct |
| 4 |
Correct |
222 ms |
35976 KB |
Output is correct |
| 5 |
Correct |
231 ms |
35976 KB |
Output is correct |
| 6 |
Execution timed out |
2557 ms |
35976 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
425 ms |
35904 KB |
Output is correct |
| 2 |
Correct |
394 ms |
35904 KB |
Output is correct |
| 3 |
Correct |
395 ms |
35904 KB |
Output is correct |
| 4 |
Correct |
402 ms |
35976 KB |
Output is correct |
| 5 |
Correct |
413 ms |
35976 KB |
Output is correct |
| 6 |
Correct |
399 ms |
35976 KB |
Output is correct |
| 7 |
Correct |
378 ms |
35976 KB |
Output is correct |
| 8 |
Correct |
449 ms |
35976 KB |
Output is correct |
| 9 |
Correct |
3 ms |
35976 KB |
Output is correct |
| 10 |
Correct |
3 ms |
35976 KB |
Output is correct |
| 11 |
Correct |
209 ms |
35976 KB |
Output is correct |
| 12 |
Correct |
223 ms |
35976 KB |
Output is correct |
| 13 |
Correct |
239 ms |
35976 KB |
Output is correct |
| 14 |
Correct |
222 ms |
35976 KB |
Output is correct |
| 15 |
Correct |
231 ms |
35976 KB |
Output is correct |
| 16 |
Execution timed out |
2557 ms |
35976 KB |
Time limit exceeded |
| 17 |
Halted |
0 ms |
0 KB |
- |
