oj.uz

Submission #4482

# Submission time Handle Problem Language Result Execution time Memory
4482 2013-10-08T13:48:11 Z pl0892029 개구리 (KOI13_frog) C++
22 / 22
 172 ms 11052 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
#define _N 100001
 
int max(int a,int b) { return a>b ? a:b; }
 
// include and define
 
int N, r, d;
int s[_N], e[_N];
 
// input
 
typedef struct coord {
    int x, y, idx;
}coord;
 
bool cmpCoord(coord A,coord B) {
    return (A.x==B.x) ? A.y < B.y : A.x < B.x;
}
 
coord frog[_N];
 
// frog
 
typedef struct edge {
    int u, v;
}edge;
 
bool cmpEdge(edge A, edge B) {
    return A.u < B.u;
}
 
edge E[_N*5];
int top=0;
 
void make_edge(int u, int v) {
    E[top].u = u;
    E[top].v = v;
    top++;
 
    E[top].u = v;
    E[top].v = u;
    top++;
}
 
// edge
 
int idxTree[1<<19], T;
 
void init(int n) {
    for(T=1;T<n;T*=2);
    for(int i=1;i<n+T;i++) idxTree[i] = -1;
}
 
int search(int s) {
    int maxValue = -1;
    s += T;
    while(s > 0) {
        maxValue = max(maxValue,idxTree[s]);
        s/=2;
    }
    return maxValue;
}
 
void update(int s, int e, int value) {
    s+=T, e+=T;
    while(s<e) {
        if(s&1) {
            idxTree[s] = max(value,idxTree[s]);
            s++;
        }
        if(!(e&1)) {
            idxTree[e] = max(value,idxTree[e]);
            e--;
        }
        s/=2, e/=2;
    }
    if(s==e) idxTree[s] = max(value,idxTree[s]);
}
 
// indexedTree
 
int values[_N*2], tmp[_N*2], n;
 
int binary_search(int key) {
    int start = 0, end = n;
    while(start < end) {
        int middle = (start+end)/2;
 
        if(values[middle] < key)
            start = middle+1;
 
        else
            end = middle;
    }
    return start;
}
 
void unique() {
    for(int i=0;i<N;i++) {
        tmp[2*i] = frog[i].y;
        tmp[2*i+1] = frog[i].y+r;
    }
 
    sort(tmp,tmp+2*N);
 
    int T = 0;
 
    values[T++] = tmp[0];
 
    for(int i=1;i<2*N;i++)
        if(tmp[i]!=tmp[i-1])
            values[T++] = tmp[i];
 
    n = T;
}
 
void swap();
 
void jumping() {
    unique();
    init(n);
    for(int i=0;i<N;i++){
        int p1 = binary_search(frog[i].y);
        int p2 = binary_search(frog[i].y+r);
 
        int v1 = search(p1);
        int v2 = search(p2);
 
         
        update(p1,p2,i);
 
        if( v1 != -1 && frog[v1].x+r+d >= frog[i].x )
            make_edge(frog[v1].idx,frog[i].idx);
        if( v2 != -1 && frog[v2].x+r+d >= frog[i].x )
            make_edge(frog[v2].idx,frog[i].idx);
    }
    swap();
    sort(frog,frog+N,cmpCoord);
}
 
// jumping
 
int Queue[_N], front, rear;
bool check[_N];
 
void getSE() {
    s[E[0].u]=0;
 
    for(int i=1;i<top;i++) {
        if( E[i].u != E[i-1].u ) {
            s[E[i].u]=i;
            e[E[i-1].u]=i;
        }
    }
    e[E[top-1].u]=top;
}
 
int getAnswer() {
    sort(E,E+top,cmpEdge);
 
    getSE();
 
    for(int i=0;i<N;i++)
        check[i] = false;
 
    front = rear = 0;
    Queue[rear++] = 0;
    check[0] = true;
 
    while(front < rear) {
        int temp = Queue[front++];
        for(int i=s[temp];i<e[temp];i++) {
            if( check[E[i].v] ) continue;
            check[E[i].v] = true;
            Queue[rear++] = E[i].v;
        }
    }
     
    int ans = 0;
 
    for(int i=0;i<N;i++) {
        if( check[i] )
            ans = max(ans,frog[i].x+frog[i].y+2*r);
    }
 
    return ans;
}
 
// getAnswer
 
void input() {
    scanf("%d %d",&N,&r);
 
    for(int i=0;i<N;i++)
        scanf("%d %d",&frog[i].x,&frog[i].y);
 
    sort(frog,frog+N,cmpCoord);
 
    for(int i=0;i<N;i++)
        frog[i].idx = i;
 
    scanf("%d",&d);
}
 
void swap() {
    for(int i=0;i<N;i++) {
        int temp = frog[i].x;
        frog[i].x = frog[i].y;
        frog[i].y = temp;
    }
}
 
int main() {
    input();
 
    jumping();
    jumping();
 
    printf("%d",getAnswer());
}

Subtask #1
1.98 / 1.98

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11052 KB Output is correct
2 Correct 0 ms 11052 KB Output is correct
3 Correct 0 ms 11052 KB Output is correct
4 Correct 0 ms 11052 KB Output is correct
5 Correct 0 ms 11052 KB Output is correct
6 Correct 0 ms 11052 KB Output is correct
7 Correct 0 ms 11052 KB Output is correct

Subtask #2
2.64 / 2.64

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11052 KB Output is correct
2 Correct 0 ms 11052 KB Output is correct
3 Correct 0 ms 11052 KB Output is correct
4 Correct 0 ms 11052 KB Output is correct
5 Correct 0 ms 11052 KB Output is correct
6 Correct 0 ms 11052 KB Output is correct
7 Correct 0 ms 11052 KB Output is correct

Subtask #3
3.52 / 3.52

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11052 KB Output is correct
2 Correct 0 ms 11052 KB Output is correct
3 Correct 0 ms 11052 KB Output is correct
4 Correct 0 ms 11052 KB Output is correct
5 Correct 0 ms 11052 KB Output is correct
6 Correct 0 ms 11052 KB Output is correct
7 Correct 4 ms 11052 KB Output is correct

Subtask #4
4.18 / 4.18

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11052 KB Output is correct
2 Correct 8 ms 11052 KB Output is correct
3 Correct 8 ms 11052 KB Output is correct
4 Correct 4 ms 11052 KB Output is correct
5 Correct 8 ms 11052 KB Output is correct
6 Correct 12 ms 11052 KB Output is correct
7 Correct 8 ms 11052 KB Output is correct

Subtask #5
4.62 / 4.62

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11052 KB Output is correct
2 Correct 4 ms 11052 KB Output is correct
3 Correct 8 ms 11052 KB Output is correct
4 Correct 8 ms 11052 KB Output is correct
5 Correct 16 ms 11052 KB Output is correct
6 Correct 16 ms 11052 KB Output is correct
7 Correct 48 ms 11052 KB Output is correct

Subtask #6
5.06 / 5.06

# Verdict Execution time Memory Grader output
1 Correct 64 ms 11052 KB Output is correct
2 Correct 100 ms 11052 KB Output is correct
3 Correct 160 ms 11052 KB Output is correct
4 Correct 100 ms 11052 KB Output is correct
5 Correct 104 ms 11052 KB Output is correct
6 Correct 164 ms 11052 KB Output is correct
7 Correct 172 ms 11052 KB Output is correct