| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 99390 |
2019-03-03T12:33:07 Z |
dantoh000 |
Park (BOI16_park) |
C++14 |
|
556 ms |
50108 KB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
vector<iii> a;
int n,m,w,h;
vi p,rk;
int numedges = 0;
void init(int n){
for (int i = 0; i < n; i++){
p.push_back(i);
rk.push_back(0);
}
}
int findset(int x){
return x == p[x] ? x : p[x] = findset(p[x]);
}
bool sameset(int x, int y){
return findset(x) == findset(y);
}
void unionset(int i, int j){
int x = findset(i);
int y= findset(j);
if (x == y) return;
numedges++;
if (rk[x] < rk[y]){
p[x] =y;
}
else{
p[y] = x;
if (rk[x] == rk[y]) rk[x]++;
}
}
int sqrt(int x){
return (int)(pow(x,0.50000000));
}
int dist(int i, int j){
int r = a[i].first, x = a[i].second.first, y = a[i].second.second;
if (j >= n){
if (j == n) return x-r;
if (j == n+1) return y-r;
if (j == n+2) return w-x-r;
if (j == n+3) return h-y-r;
}
else{
int r1 = a[j].first, x1 = a[j].second.first, y1 = a[j].second.second;
return sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y)) - r1-r;
}
}
int finder(int a, int b){
if (a > b) swap(a,b);
if (a == 0 && b == 1) return 0;
if (a == 0 && b == 2) return 1;
if (a == 0 && b == 3) return 2;
if (a == 1 && b == 2) return 3;
if (a == 1 && b == 3) return 4;
if (a == 2 && b == 3) return 5;
}
main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
//freopen("testdebug.txt","w",stdout);
scanf("%lld%lld%lld%lld",&n,&m,&w,&h);
for (int i = 0; i < n; i++){
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
a.push_back(iii(z,ii(x,y)));
}
vector<iii> edgelist;
for (int i = 0; i < n; i++){
for (int j = i+1; j < n+4; j++){
//printf("dist from %lld %lld = %lld\n",i,j,dist(i,j));
edgelist.push_back(iii(dist(i,j),ii(i,j)));
}
}
sort(edgelist.begin(),edgelist.end());
init(n+4);
bool b[6];
b[0] = b[1] = b[2] = b[3] = b[4] = b[5] = true;
int thres[6];
for (auto cur : edgelist){
int d = cur.first, x = cur.second.first, y = cur.second.second;
//if (!sameset(x,y)) printf("%lld %lld %lld\n",d,x,y);
unionset(x,y);
if (b[0] && (sameset(n,n+1) || sameset(n+1,n+3) || sameset(n+1,n+2))){
b[0] = false;
thres[0] = d;
}
if (b[1] && (sameset(n,n+1) || sameset(n+1,n+3) || sameset(n+2,n+3) || sameset(n,n+2))){
b[1] = false;
thres[1] = d;
}
if (b[2] && (sameset(n,n+1) || sameset(n,n+2) || sameset(n,n+3))){
b[2] = false;
thres[2] = d;
}
if (b[3] && (sameset(n+2,n+1) || sameset(n+2,n) || sameset(n+2,n+3))){
b[3] = false;
thres[3] = d;
}
if (b[4] && (sameset(n+2,n+1) || sameset(n+1,n+3) || sameset(n,n+3) || sameset(n,n+2))){
b[4] = false;
thres[4] = d;
}
if (b[5] && (sameset(n+3,n) || sameset(n+3,n+1) || sameset(n+3,n+2))){
b[5] = false;
thres[5] = d;
}
}
for (int i = 0; i < 6; i++){
//printf("%lld ", thres[i]);
}
for (int i = 0; i < m; i++){
int r,e;
scanf("%lld%lld",&r,&e);
r *= 2;
e--;
for (int i = 0; i < 4; i++){
//printf("%lld %lld %lld\n",e,i,finder(e,i));
if (e == i || r <= thres[finder(e,i)]){
printf("%lld",i+1);
}
}
printf("\n");
}
}
Compilation message
park.cpp:61:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
park.cpp: In function 'long long int dist(long long int, long long int)':
park.cpp:51:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
park.cpp: In function 'long long int finder(long long int, long long int)':
park.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
park.cpp: In function 'int main()':
park.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld",&n,&m,&w,&h);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld",&x,&y,&z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&r,&e);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
499 ms |
49844 KB |
Output is correct |
| 2 |
Correct |
487 ms |
49760 KB |
Output is correct |
| 3 |
Correct |
510 ms |
49884 KB |
Output is correct |
| 4 |
Correct |
497 ms |
49884 KB |
Output is correct |
| 5 |
Correct |
473 ms |
49728 KB |
Output is correct |
| 6 |
Correct |
493 ms |
49920 KB |
Output is correct |
| 7 |
Correct |
514 ms |
49752 KB |
Output is correct |
| 8 |
Correct |
506 ms |
49884 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
1396 KB |
Output is correct |
| 2 |
Correct |
54 ms |
1280 KB |
Output is correct |
| 3 |
Correct |
54 ms |
1280 KB |
Output is correct |
| 4 |
Correct |
63 ms |
2420 KB |
Output is correct |
| 5 |
Correct |
67 ms |
2420 KB |
Output is correct |
| 6 |
Correct |
56 ms |
2420 KB |
Output is correct |
| 7 |
Correct |
50 ms |
1784 KB |
Output is correct |
| 8 |
Correct |
50 ms |
1788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
499 ms |
49844 KB |
Output is correct |
| 2 |
Correct |
487 ms |
49760 KB |
Output is correct |
| 3 |
Correct |
510 ms |
49884 KB |
Output is correct |
| 4 |
Correct |
497 ms |
49884 KB |
Output is correct |
| 5 |
Correct |
473 ms |
49728 KB |
Output is correct |
| 6 |
Correct |
493 ms |
49920 KB |
Output is correct |
| 7 |
Correct |
514 ms |
49752 KB |
Output is correct |
| 8 |
Correct |
506 ms |
49884 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Correct |
56 ms |
1396 KB |
Output is correct |
| 12 |
Correct |
54 ms |
1280 KB |
Output is correct |
| 13 |
Correct |
54 ms |
1280 KB |
Output is correct |
| 14 |
Correct |
63 ms |
2420 KB |
Output is correct |
| 15 |
Correct |
67 ms |
2420 KB |
Output is correct |
| 16 |
Correct |
56 ms |
2420 KB |
Output is correct |
| 17 |
Correct |
50 ms |
1784 KB |
Output is correct |
| 18 |
Correct |
50 ms |
1788 KB |
Output is correct |
| 19 |
Correct |
527 ms |
50076 KB |
Output is correct |
| 20 |
Correct |
522 ms |
50012 KB |
Output is correct |
| 21 |
Correct |
555 ms |
50108 KB |
Output is correct |
| 22 |
Correct |
527 ms |
50096 KB |
Output is correct |
| 23 |
Correct |
530 ms |
50012 KB |
Output is correct |
| 24 |
Correct |
556 ms |
50012 KB |
Output is correct |
