Submission #68970

#	Time	Username	Problem	Language	Result	Execution time	Memory
68970		Vahan	Park (BOI16_park)	C++17	0 / 100	884 ms	263168 KiB

park

#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<long long,long long>,long long> aa[100005];
string ss[100005];
vector< pair <double,pair<long long,long long> > > 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(long long j=1;j<=4;j++)
        {
            if(k[aa[i].first.second][j]==0 && k[j][aa[i].first.second]==0)
                ss[aa[i].second]+=j+'0';
        }
        for(long long j=1;j<=4;j++)
        {
            for(long long e=1;e<=4;e++)
                k[j][e]=0;
        }
    }
    for(long long i=1;i<=m;i++)
        cout<<ss[i]<<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 (stderr)

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]
 }
 ^

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42