| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 99415 |
2019-03-03T19:31:32 Z |
errorgorn |
Park (BOI16_park) |
C++14 |
|
214 ms |
69276 KB |
#include <cstdio>
#include <utility>
#include <queue>
#include <cmath>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef pair<ii,int> iiI;
typedef pair<long double,ii> dii;
int n,m,w,h,p[2010],r[2010];
iii coord[2010];
priority_queue<dii,vector<dii>, greater<dii> > pq;
iiI ppl[100005];
string toprint[100005];
int parent(int i){ return (p[i]==i)? i:p[i]=parent(p[i]);}
bool connected(int i,int j){
return parent(i)==parent(j);
}
void join(int i,int j){
if (connected(i,j)) return;
i=parent(i);
j=parent(j);
if (r[i]<r[j]){
p[i]=j;
}
else{
p[j]=i;
if (r[i]==r[j]) r[i]++;
}
}
long double sq(long long i){
return i*i;
}
int main(){
//freopen("input.txt","r",stdin);
scanf("%d%d%d%d",&n,&m,&w,&h);
int a,b,c;
n+=4;
for (int x=0;x<n;x++) p[x]=x;
for (int x=4;x<n;x++){
scanf("%d%d%d",&a,&b,&c);
coord[x]=iii(c,ii(a,b));
pq.push(dii (sq(a-c),ii (x,0)));
pq.push(dii (sq(b-c),ii (x,1)));
pq.push(dii (sq(w-a-c),ii (x,2)));
pq.push(dii (sq(h-b-c),ii (x,3)));
for (int y=4;y<x;y++){
pq.push(dii(sqrtl(sq(coord[y].second.first-a)+sq(coord[y].second.second-b))-c-coord[y].first ,ii(x,y)));
}
}
long double d;
for (int x=0;x<m;x++){
scanf("%d%d",&ppl[x].first.first,&ppl[x].first.second);
ppl[x].second=x;
}
sort(&ppl[0],&ppl[m]);
for (int x=0;x<m;x++){
d=ppl[x].first.first<<1;
while (!pq.empty() && pq.top().first<d){
//printf("%Lf %d %d\n",pq.top().first,pq.top().second.first,pq.top().second.second);
join(pq.top().second.first,pq.top().second.second);
pq.pop();
}
if (ppl[x].first.second==1){
toprint[ppl[x].second]+=("1");
if (!connected(0,1) && !connected(1,2) && !connected(1,3)) toprint[ppl[x].second]+=("2");
if (!connected(0,1) && !connected(2,3) && !connected(0,2) && !connected(1,3)) toprint[ppl[x].second]+=("3");
if (!connected(0,3) && !connected(0,2) && !connected(0,2)) toprint[ppl[x].second]+=("4");
}
else if (ppl[x].first.second==2){
if (!connected(0,1) && !connected(1,2) && !connected(1,3)) toprint[ppl[x].second]+=("1");
toprint[ppl[x].second]+=("2");
if (!connected(1,2) && !connected(2,3) && !connected(0,2)) toprint[ppl[x].second]+=("3");
if (!connected(0,3) && !connected(1,2) && !connected(0,2) && !connected(1,3)) toprint[ppl[x].second]+=("4");
}
else if (ppl[x].first.second==3){
if (!connected(0,1) && !connected(1,2) && !connected(0,2) && !connected(1,3)) toprint[ppl[x].second]+=("1");
if (!connected(1,2) && !connected(2,3) && !connected(0,2)) toprint[ppl[x].second]+=("2");
toprint[ppl[x].second]+=("3");
if (!connected(0,3) && !connected(2,3) && !connected(1,3)) toprint[ppl[x].second]+=("4");
}
else{
if (!connected(0,3) && !connected(0,2) && !connected(0,2)) toprint[ppl[x].second]+=("1");
if (!connected(0,3) && !connected(1,2) && !connected(0,2) && !connected(1,3)) toprint[ppl[x].second]+=("2");
if (!connected(0,3) && !connected(2,3) && !connected(1,3)) toprint[ppl[x].second]+=("3");
toprint[ppl[x].second]+=("4");
}
}
for (int x=0;x<m;x++){
cout<<toprint[x]<<'\n';
}
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d",&n,&m,&w,&h);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&a,&b,&c);
~~~~~^~~~~~~~~~~~~~~~~~~
park.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&ppl[x].first.first,&ppl[x].first.second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
69276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
5888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
69276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
