oj.uz

Submission #130177

# Submission time Handle Problem Language Result Execution time Memory
130177 2019-07-14T07:51:48 Z white9572 개구리 (KOI13_frog) C++14
16.94 / 22
 1000 ms 11680 KB 
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

vector <int> vec[100002];
int n, r, d, v[100002], ans=0, num[100002], m, check[100002], qx[100002];

struct A{
    int x, y;
} data[100002];

bool cmp(const A &p1, const A &p2){
    if(p1.x<p2.x){
        return 1;
    }
    else if(p1.x==p2.x){
        return p1.y<p2.y;
    }
    else{
        return 0;
    }
}

int main()
{
    int i, j;
    scanf("%d %d", &n, &r);
    for(i=1 ; i<=n ; i++)
    {
        scanf("%d %d", &data[i].x, &data[i].y);
    }
    scanf("%d", &d);
    sort(data+1, data+1+n, cmp);
    for(i=1 ; i<=n ; i++)
    {
        for(j=i+1 ; j<=n ; j++)
        {
            if(data[j].x<=data[i].x+r+d && data[j].y>=data[i].y-r && data[j].y<=data[i].y+r)
            {
                vec[i].push_back(j);
                vec[j].push_back(i);
            }
            else if(data[j].x<=data[i].x+r && data[j].y>=data[i].y-r-d && data[j].y<=data[i].y+r+d)
            {
                vec[i].push_back(j);
                vec[j].push_back(i);
            }
            else if(data[j].x>data[i].x+d+r)
            {
                break;
            }
        }
    }
    int head=0, tail=0;
    qx[head++]=1;
    v[1]=1;
    while(head!=tail)
    {
        int x=qx[tail++];
        for(i=0 ; i<vec[x].size() ; i++)
        {
            if(v[vec[x][i]]==0)
            {
                qx[head++]=vec[x][i];
                v[vec[x][i]]=1;
                if(ans<data[vec[x][i]].x+data[vec[x][i]].y+2*r)
                {
                    ans=data[vec[x][i]].x+data[vec[x][i]].y+2*r;
                }
            }
        }
    }
    printf("%d", ans);
    return 0;
}

Compilation message

frog.cpp: In function 'int main()':
frog.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0 ; i<vec[x].size() ; i++)
                   ~^~~~~~~~~~~~~~
frog.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &r);
     ~~~~~^~~~~~~~~~~~~~~~~
frog.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &data[i].x, &data[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
frog.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &d);
     ~~~~~^~~~~~~~~~

Subtask #1
1.98 / 1.98

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

Subtask #2
2.64 / 2.64

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

Subtask #3
3.52 / 3.52

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

Subtask #4
4.18 / 4.18

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2876 KB Output is correct
2 Correct 7 ms 2808 KB Output is correct
3 Correct 10 ms 2936 KB Output is correct
4 Correct 7 ms 2936 KB Output is correct
5 Correct 9 ms 2808 KB Output is correct
6 Correct 28 ms 4476 KB Output is correct
7 Correct 76 ms 4856 KB Output is correct

Subtask #5
4.62 / 4.62

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2936 KB Output is correct
2 Correct 10 ms 3124 KB Output is correct
3 Correct 8 ms 2808 KB Output is correct
4 Correct 23 ms 3972 KB Output is correct
5 Correct 12 ms 3064 KB Output is correct
6 Correct 70 ms 6424 KB Output is correct
7 Correct 42 ms 3804 KB Output is correct

Subtask #6
0 / 5.06

# Verdict Execution time Memory Grader output
1 Correct 374 ms 10536 KB Output is correct
2 Correct 98 ms 5072 KB Output is correct
3 Execution timed out 1077 ms 11680 KB Time limit exceeded
4 Halted 0 ms 0 KB -