oj.uz

답안 #46285

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
46285 2018-04-18T18:35:59 Z ikura355 Park (BOI16_park) C++14
27 / 100
 2500 ms 35976 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);
        cur = 0;
        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:74: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

# 결과 실행 시간 메모리 Grader output
1 Correct 425 ms 35904 KB Output is correct
2 Correct 394 ms 35904 KB Output is correct
3 Correct 395 ms 35904 KB Output is correct
4 Correct 402 ms 35976 KB Output is correct
5 Correct 413 ms 35976 KB Output is correct
6 Correct 399 ms 35976 KB Output is correct
7 Correct 378 ms 35976 KB Output is correct
8 Correct 449 ms 35976 KB Output is correct
9 Correct 3 ms 35976 KB Output is correct
10 Correct 3 ms 35976 KB Output is correct

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 209 ms 35976 KB Output is correct
2 Correct 223 ms 35976 KB Output is correct
3 Correct 239 ms 35976 KB Output is correct
4 Correct 222 ms 35976 KB Output is correct
5 Correct 231 ms 35976 KB Output is correct
6 Execution timed out 2557 ms 35976 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 425 ms 35904 KB Output is correct
2 Correct 394 ms 35904 KB Output is correct
3 Correct 395 ms 35904 KB Output is correct
4 Correct 402 ms 35976 KB Output is correct
5 Correct 413 ms 35976 KB Output is correct
6 Correct 399 ms 35976 KB Output is correct
7 Correct 378 ms 35976 KB Output is correct
8 Correct 449 ms 35976 KB Output is correct
9 Correct 3 ms 35976 KB Output is correct
10 Correct 3 ms 35976 KB Output is correct
11 Correct 209 ms 35976 KB Output is correct
12 Correct 223 ms 35976 KB Output is correct
13 Correct 239 ms 35976 KB Output is correct
14 Correct 222 ms 35976 KB Output is correct
15 Correct 231 ms 35976 KB Output is correct
16 Execution timed out 2557 ms 35976 KB Time limit exceeded
17 Halted 0 ms 0 KB -