| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 68975 |
2018-08-19T11:48:24 Z |
Vahan |
Park (BOI16_park) |
C++17 |
|
946 ms |
263168 KB |
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
long long n,m,k[6][6],u[3000],w,h,x[4000],y[4000],r[4000],p[4000],sz[4000];
pair<pair<int,int>,int> aa[100005];
int pat[100005][5];
vector< pair <double,pair<int,int> > > g;
void stug(long long a,long long b)
{
if(a==n+1)
{
if(b==n+2)
{
k[4][3]=1;
k[4][2]=1;
k[4][1]=1;
}
if(b==n+3)
{
k[4][1]=1;
k[4][2]=1;
k[3][1]=1;
k[3][2]=1;
}
if(b==n+4)
{
k[1][4]=1;
k[1][3]=1;
k[1][2]=1;
}
}
if(a==n+2)
{
if(b==n+3)
{
k[3][1]=1;
k[3][2]=1;
k[3][4]=1;
}
if(b==n+4)
{
k[3][1]=1;
k[3][4]=1;
k[2][1]=1;
k[2][4]=1;
}
}
if(a==n+3)
{
if(b==n+4)
{
k[2][1]=1;
k[2][3]=1;
k[2][4]=1;
}
}
}
double dis(long long a,long long b)
{
return (double)sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]))-r[a]-r[b];
}
void create(long long a)
{
sz[a]=0;
p[a]=a;
}
long long findparent(long long a)
{
if(a==p[a])
return a;
p[a]=findparent(p[a]);
}
void unionset(long long a,long long b)
{
a=findparent(a);
b=findparent(b);
if(a==b)
return;
if(sz[a]>=sz[b])
{
p[b]=a;
sz[a]+=sz[b];
}
else
{
p[a]=b;
sz[b]+=sz[a];
}
}
int main()
{
cin>>n>>m;
cin>>w>>h;
for(long long i=1;i<=n;i++)
cin>>x[i]>>y[i]>>r[i];
for(long long i=1;i<n;i++)
{
for(long long j=i+1;j<=n;j++)
{
double e=dis(i,j);
g.push_back(make_pair(e,make_pair(i,j)));
}
}
for(long long i=1;i<=n;i++)
{
g.push_back(make_pair(x[i]-r[i],make_pair(i,n+1)));
g.push_back(make_pair(h-y[i]-r[i],make_pair(i,n+2)));
g.push_back(make_pair(w-x[i]-r[i],make_pair(i,n+3)));
g.push_back(make_pair(y[i]-r[i],make_pair(i,n+4)));
}
sort(g.begin(),g.end());
for(long long i=1;i<=m;i++)
{
cin>>aa[i].first.first>>aa[i].first.second;
aa[i].second=i;
aa[i].first.first*=2;
}
sort(aa+1,aa+m+1);
long long t=0;
for(long long i=1;i<=n+4;i++)
create(i);
for(long long i=1;i<=m;i++)
{
while((double)(aa[i].first.first)>g[t].first)
{
unionset(g[t].second.first,g[t].second.second);
t++;
}
for(long long j=n+1;j<n+4;j++)
{
for(long long e=j+1;e<=n+4;e++)
{
if(findparent(e)==findparent(j))
stug(j,e);
}
}
for(int j=1;j<=4;j++)
{
if(k[aa[i].first.second][j]==0 && k[j][aa[i].first.second]==0)
pat[aa[i].second][j]=1;
}
for(int j=1;j<=4;j++)
{
for(int e=1;e<=4;e++)
k[j][e]=0;
}
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=4;j++)
if(pat[i][j]==1)
cout<<j;
cout<<endl;
}
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 'long long int findparent(long long int)':
park.cpp:75:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
946 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
668 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
946 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
