Submission #99426

#	Time	Username	Problem	Language	Result	Execution time	Memory
99426		errorgorn	Park (BOI16_park)	C++14	100 / 100	648 ms	28892 KiB

park

#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<int,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 (a-c,ii (x,0)));
        pq.push(dii (b-c,ii (x,1)));
        pq.push(dii (w-a-c,ii (x,2)));
        pq.push(dii (h-b-c,ii (x,3)));
        for (int y=4;y<x;y++){
            pq.push(dii((int)sqrtl(sq(coord[y].second.first-a)+sq(coord[y].second.second-b))-c-coord[y].first ,ii(x,y)));
        }
    }
    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++){
        a=ppl[x].first.first<<1;
        while (!pq.empty() && pq.top().first<a){
            //printf("%d %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,1) && !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(3,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,1)) 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 (stderr)

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:55: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);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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