oj.uz

답안 #4951

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4951 2014-01-23T13:21:52 Z hana5505 개구리 (KOI13_frog) C++
22 / 22
 220 ms 12436 KB 
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
vector<int> ve[100001];
queue<int> q;
struct pp{
    int x, y;
    int idx;
}leaves[100001];
int index[210001];
int que[210001];
int tree[600001];
int chk[100001];
int n, r, d, len;
int max_int(int a, int b){
    if (a > b) return a;
    return b;
}
int ab(int k){
    if (k<0) return -k;
    return k;
}
bool cmp(struct pp a, struct pp b)
{
    if (a.x == b.x) return a.y<b.y;
    return a.x<b.x;
}
int tree_find(int t, int c, int left, int right)
{
    if (left == right) return tree[c];
    if (tree[c] != -1){
        tree[c * 2] = max_int(tree[c * 2], tree[c]);
        tree[c * 2 + 1] = max_int(tree[c * 2 + 1], tree[c]);
    }
    if (t <= (left + right) / 2) return tree_find(t, c * 2, left, (left + right) / 2);
    else return tree_find(t, c * 2 + 1, (left + right) / 2 + 1, right);
}
void renew(int left, int right, int c, int t, int f_left, int f_right)
{
    if (f_left <= left && right <= f_right){
        tree[c] = t;
        return;
    }
    if (f_left <= (left + right) / 2) renew(left, (left + right) / 2, c * 2, t, f_left, f_right);
    if (f_right >= (left + right) / 2 + 1) renew((left + right) / 2 + 1, right, c * 2 + 1, t, f_left, f_right);
}
int ret_index(int k)
{
    return lower_bound(index + 1, index + len + 1, k) - index;
}
void get_vertex()
{
    int i, tmp, size, a, b;
 
    for (i = 1; i <= n; i++){
        que[2 * i - 1] = leaves[i].y;
        que[2 * i] = leaves[i].y + r;
    }
    sort(que + 1, que + 2 * n + 1);
 
    len = 0;
    index[++len] = que[1];
    tmp = que[1];
    for (i = 2; i <= 2 * n; i++){
        if (que[i] != tmp){
            index[++len] = que[i];
            tmp = que[i];
        }
    }
    sort(leaves + 1, leaves + n + 1, cmp);
    for (size = 1; size <= len; size *= 2);
    for (i = 1; i <= size * 2; i++) tree[i] = -1;
 
    for (i = 1; i <= n; i++){
        a = tree_find(ret_index(leaves[i].y), 1, 1, size);
        b = tree_find(ret_index(leaves[i].y + r), 1, 1, size);
        if (a != -1 && ab(leaves[i].x - leaves[a].x) <= r + d){
            ve[leaves[i].idx].push_back(leaves[a].idx);
            ve[leaves[a].idx].push_back(leaves[i].idx);
        }
        if (b != -1 && ab(leaves[i].x - leaves[b].x) <= r + d){
            ve[leaves[i].idx].push_back(leaves[b].idx);
            ve[leaves[b].idx].push_back(leaves[i].idx);
        }
        renew(1, size, 1, i, ret_index(leaves[i].y), ret_index(leaves[i].y + r));
    }
}
int main()
{
    int i, j, tmp, tt, mx = 0;
    int st;
 
    scanf("%d %d", &n, &r);
    for (i = 1; i <= n; i++){
        scanf("%d %d", &leaves[i].x, &leaves[i].y);
        leaves[i].idx = i;
        if (leaves[i].x == 0 && leaves[i].y == 0) st = i;
    }
    scanf("%d", &d);
 
    get_vertex();
    for (i = 1; i <= n; i++){
        tmp = leaves[i].x;
        leaves[i].x = leaves[i].y;
        leaves[i].y = tmp;
    }
    get_vertex();
 
    tt = st;
    q.push(tt);
    chk[tt] = 1;
    while (!q.empty()){
        tt = q.front();
        q.pop();
        for (i = 0; i<ve[tt].size(); i++){
            if (chk[ve[tt][i]] == 0){
                chk[ve[tt][i]] = 1;
                tmp = ve[tt][i];
                q.push(tmp);
            }
        }
    }
 
    for (i = 1; i <= n; i++){
        if (chk[leaves[i].idx] == 1){
            if (leaves[i].x + leaves[i].y >= mx) mx = leaves[i].x + leaves[i].y;
        }
    }
 
    printf("%d", mx + 2 * r);
}

Subtask #1
1.98 / 1.98

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 9136 KB Output is correct
2 Correct 0 ms 9136 KB Output is correct
3 Correct 0 ms 9136 KB Output is correct
4 Correct 0 ms 9136 KB Output is correct
5 Correct 0 ms 9136 KB Output is correct
6 Correct 0 ms 9136 KB Output is correct
7 Correct 0 ms 9136 KB Output is correct

Subtask #2
2.64 / 2.64

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 9136 KB Output is correct
2 Correct 0 ms 9136 KB Output is correct
3 Correct 0 ms 9136 KB Output is correct
4 Correct 0 ms 9136 KB Output is correct
5 Correct 0 ms 9136 KB Output is correct
6 Correct 0 ms 9136 KB Output is correct
7 Correct 0 ms 9136 KB Output is correct

Subtask #3
3.52 / 3.52

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 9136 KB Output is correct
2 Correct 0 ms 9136 KB Output is correct
3 Correct 0 ms 9136 KB Output is correct
4 Correct 0 ms 9136 KB Output is correct
5 Correct 4 ms 9136 KB Output is correct
6 Correct 4 ms 9136 KB Output is correct
7 Correct 8 ms 9136 KB Output is correct

Subtask #4
4.18 / 4.18

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9136 KB Output is correct
2 Correct 12 ms 9136 KB Output is correct
3 Correct 12 ms 9136 KB Output is correct
4 Correct 8 ms 9136 KB Output is correct
5 Correct 8 ms 9136 KB Output is correct
6 Correct 16 ms 9400 KB Output is correct
7 Correct 12 ms 9268 KB Output is correct

Subtask #5
4.62 / 4.62

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9136 KB Output is correct
2 Correct 4 ms 9136 KB Output is correct
3 Correct 12 ms 9136 KB Output is correct
4 Correct 8 ms 9136 KB Output is correct
5 Correct 24 ms 9136 KB Output is correct
6 Correct 28 ms 9400 KB Output is correct
7 Correct 64 ms 9400 KB Output is correct

Subtask #6
5.06 / 5.06

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 10324 KB Output is correct
2 Correct 144 ms 9532 KB Output is correct
3 Correct 220 ms 12304 KB Output is correct
4 Correct 176 ms 9532 KB Output is correct
5 Correct 164 ms 9796 KB Output is correct
6 Correct 216 ms 12436 KB Output is correct
7 Correct 216 ms 12436 KB Output is correct