Submission #46286

#	Time	Username	Problem	Language	Result	Execution time	Memory
46286		ikura355	Park (BOI16_park)	C++14	100 / 100	511 ms	48188 KiB

park

//aiming for 100 marks
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10;
const int maxq = 1e5 + 5;
const double eps = 1e-7;
struct point {
	double x, y, r;
};
struct edge {
    int x, y;
    double dist;
    edge(int _x = 0, int _y = 0, double _dist = 0) {
        x = _x; y = _y; dist = _dist;
    }
};
int n,m;
double w,h;
point p[maxn];
double fat[maxq];
int ent[maxq];

int ord[maxq];
vector<edge> hub;

int head[maxn];
int bad[10], con[10][10];

vector<int> ans[maxq];

double cut(point x, point y) {
	return sqrt((x.x-y.x)*(x.x-y.x) + (x.y-y.y)*(x.y-y.y));
}
bool noey(double x, double y) {
    return (y-x)>eps;
}
int findhead(int x) {
	if(head[x]==x) return x;
	return head[x] = findhead(head[x]);
}
bool cmp1(int x, int y) {
    return fat[x] < fat[y];
}
bool cmp2(edge x, edge y) {
    return x.dist < y.dist;
}
int main() {
	scanf("%d%d%lf%lf",&n,&m,&w,&h);
	for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r);
	for(int tnum=1;tnum<=m;tnum++) scanf("%lf%d",&fat[tnum],&ent[tnum]), fat[tnum] *= 2.0;
    //prep
    for(int i=1;i<=m;i++) ord[i] = i;
    sort(&ord[1],&ord[m+1],cmp1);
    //tree - tree
    for(int i=1;i<=n;i++) {
        for(int j=i+1;j<=n;j++) {
            hub.push_back(edge(i,j,cut(p[i],p[j])-p[i].r-p[j].r));
        }
    }
    //tree - edge
    for(int i=1;i<=n;i++) {
        hub.push_back(edge(i,n+1,p[i].y-p[i].r));
        hub.push_back(edge(i,n+2,w-p[i].x-p[i].r));
        hub.push_back(edge(i,n+3,h-p[i].y-p[i].r));
        hub.push_back(edge(i,n+4,p[i].x-p[i].r));
    }
    sort(hub.begin(),hub.end(),cmp2);
    //solve
    for(int i=1;i<=n+4;i++) head[i] = i;
    for(int rep=1,cur=0;rep<=m;rep++) {
        int tnum = ord[rep];
//        printf("solve for %d\n",tnum);
        while(cur<hub.size() && noey(hub[cur].dist, fat[tnum])) {
//            printf("\tadd edge %d %d\n",hub[cur].x,hub[cur].y);
            head[findhead(hub[cur].x)] = findhead(hub[cur].y);
            cur++;
        }
        //update connection
        int id = 0;
        for(int i=1;i<=4;i++) {
            for(int j=i+1;j<=4;j++) {
                bad[++id] = findhead(n+i)==findhead(n+j);
            }
        }
        for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) con[i][j] = 1;
        if(bad[1] || bad[2] || bad[3]) con[1][2] = con[2][1] = 0;
        if(bad[2] || bad[3] || bad[4] || bad[5]) con[1][3] = con[3][1] = 0;
        if(bad[3] || bad[5] || bad[6]) con[1][4] = con[4][1] = 0;
        if(bad[1] || bad[4] || bad[5]) con[2][3] = con[3][2] = 0;
        if(bad[1] || bad[2] || bad[5] || bad[6]) con[2][4] = con[4][2] = 0;
        if(bad[2] || bad[4] || bad[6]) con[3][4] = con[4][3] = 0;
        //show
//        id = 0;
//        for(int i=1;i<=4;i++) {
//            for(int j=i+1;j<=4;j++) {
//                printf("\t%d - %d : %d\n",i,j,bad[++id]);
//            }
//        }
		//answer
		for(int i=1;i<=4;i++) if(con[ent[tnum]][i]) ans[tnum].push_back(i);
	}
	for(int i=1;i<=m;i++) {
        for(auto x : ans[i]) printf("%d",x);
        printf("\n");
	}
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:73:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(cur<hub.size() && noey(hub[cur].dist, fat[tnum])) {
               ~~~^~~~~~~~~~~
park.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lf%lf",&n,&m,&w,&h);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:49:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:50:69: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int tnum=1;tnum<=m;tnum++) scanf("%lf%d",&fat[tnum],&ent[tnum]), fat[tnum] *= 2.0;
                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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