Submission #66392

#	Time	Username	Problem	Language	Result	Execution time	Memory
66392		ansol4328	문명 (KOI17_civilization)	C++98	54 / 100	1066 ms	44660 KiB

civilization

#include<stdio.h>
#include<memory.h>
#include<queue>

using namespace std;

int n, k;
int visit[2002][2002];

struct uf
{
    int p[4000002];
    int cnt;
    bool st[4000002];
    void setup(int a)
    {
        cnt=a;
        memset(p,-1,sizeof(p));
        memset(st,false,sizeof(st));
    }
    int f(int v)
    {
        if(p[v]==-1) return v;
        p[v]=f(p[v]);
        return p[v];
    }
    void u(int v1, int v2) // v2 subtree -> v1 subtree
    {
        v1=f(v1);
        v2=f(v2);
        if(v1==v2) return;
        if(st[v2]) cnt--;
        p[v2]=v1;
    }
};

uf T;
queue<int> Q;

int main()
{
    scanf("%d %d",&n,&k);
    T.setup(k);
    for(int i=0 ; i<k ; i++)
    {
        int x, y;
        scanf("%d %d",&y,&x);
        T.st[(y-1)*n+x-1]=true;
        Q.push((y-1)*n+x-1);
        visit[y][x]=1;
    }
    int res=1;
    int dy[4]={-1,0,1,0};
    int dx[4]={0,1,0,-1};
    while(T.cnt!=1)
    {
        int y=Q.front()/n+1;
        int x=Q.front()%n+1;
        Q.pop();
        res=max(res,visit[y][x]);
        for(int i=0 ; i<4 ; i++)
        {
            if(!(y+dy[i]>=1 && y+dy[i]<=n && x+dx[i]>=1 && x+dx[i]<=n)) continue;
            if(visit[y+dy[i]][x+dx[i]]==0)
            {
                visit[y+dy[i]][x+dx[i]]=visit[y][x]+1;
                T.u((y-1)*n+x-1,(y+dy[i]-1)*n+x+dx[i]-1);
                Q.push((y+dy[i]-1)*n+x+dx[i]-1);
            }
            else if(visit[y+dy[i]][x+dx[i]]<visit[y][x]+1)
            {
                T.u((y-1)*n+x-1,(y+dy[i]-1)*n+x+dx[i]-1);
                res=max(res,visit[y][x]);
            }
            if(T.cnt==1) break;
        }
    }
    printf("%d",res-1);
    return 0;
}

Compilation message (stderr)

civilization.cpp: In function 'int main()':
civilization.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~~
civilization.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&y,&x);
         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 35 / 35
• Subtask 3: 0 / 46