Submission #4951

#	Time	Username	Problem	Language	Result	Execution time	Memory
4951		hana5505	개구리 (KOI13_frog)	C++98	22 / 22	220 ms	12436 KiB

frog

#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
• Subtask 2: 2.64 / 2.64
• Subtask 3: 3.52 / 3.52
• Subtask 4: 4.18 / 4.18
• Subtask 5: 4.62 / 4.62
• Subtask 6: 5.06 / 5.06