Submission #130177

#	Time	Username	Problem	Language	Result	Execution time	Memory
130177		white9572	개구리 (KOI13_frog)	C++14	16.94 / 22	1077 ms	11680 KiB

frog

#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 (stderr)

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
• 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: 0 / 5.06