oj.uz

Submission #46286

# Submission time Handle Problem Language Result Execution time Memory
46286 2018-04-18T18:37:04 Z ikura355 Park (BOI16_park) C++14
100 / 100
 511 ms 48188 KB 
//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

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 35772 KB Output is correct
2 Correct 388 ms 35884 KB Output is correct
3 Correct 395 ms 35884 KB Output is correct
4 Correct 395 ms 35940 KB Output is correct
5 Correct 395 ms 35940 KB Output is correct
6 Correct 395 ms 35940 KB Output is correct
7 Correct 379 ms 35940 KB Output is correct
8 Correct 372 ms 35940 KB Output is correct
9 Correct 3 ms 35940 KB Output is correct
10 Correct 3 ms 35940 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 35940 KB Output is correct
2 Correct 106 ms 35940 KB Output is correct
3 Correct 104 ms 35940 KB Output is correct
4 Correct 110 ms 35940 KB Output is correct
5 Correct 105 ms 35940 KB Output is correct
6 Correct 104 ms 35940 KB Output is correct
7 Correct 96 ms 35940 KB Output is correct
8 Correct 123 ms 35940 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 35772 KB Output is correct
2 Correct 388 ms 35884 KB Output is correct
3 Correct 395 ms 35884 KB Output is correct
4 Correct 395 ms 35940 KB Output is correct
5 Correct 395 ms 35940 KB Output is correct
6 Correct 395 ms 35940 KB Output is correct
7 Correct 379 ms 35940 KB Output is correct
8 Correct 372 ms 35940 KB Output is correct
9 Correct 3 ms 35940 KB Output is correct
10 Correct 3 ms 35940 KB Output is correct
11 Correct 107 ms 35940 KB Output is correct
12 Correct 106 ms 35940 KB Output is correct
13 Correct 104 ms 35940 KB Output is correct
14 Correct 110 ms 35940 KB Output is correct
15 Correct 105 ms 35940 KB Output is correct
16 Correct 104 ms 35940 KB Output is correct
17 Correct 96 ms 35940 KB Output is correct
18 Correct 123 ms 35940 KB Output is correct
19 Correct 497 ms 42996 KB Output is correct
20 Correct 491 ms 44012 KB Output is correct
21 Correct 511 ms 45100 KB Output is correct
22 Correct 497 ms 46180 KB Output is correct
23 Correct 497 ms 47076 KB Output is correct
24 Correct 483 ms 48188 KB Output is correct