oj.uz

답안 #49016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49016 2018-05-21T09:47:35 Z okaybody10 문명 (KOI17_civilization) C++
0 / 100
 3 ms 760 KB 
#include<stdio.h>
int map_size,civ;
int Q[4000010][2],front,rear;
int Q2[1000010][2],front2,rear2;
int start[100010][2];
int map[2010][2010],vis[100010];
int extend(int a,int x,int y)
{
    if(x==0 || x==map_size+1 || y==0 || y==map_size+1) return 0;
    if(map[x][y]!=0) return 0;
    map[x][y]=a;
    Q[rear][0]=x; Q[rear++][1]=y;
    return 1;
}
 
void find(int x,int y)
{
    if(map[x+1][y])
    {
        if(map[x][y]>map[x+1][y]) vis[map[x][y]]=vis[map[x+1][y]];
        else vis[map[x+1][y]]=vis[map[x][y]];
    }
    if(map[x-1][y])
    {
        if(map[x][y]>map[x-1][y]) vis[map[x][y]]=vis[map[x-1][y]];
        else vis[map[x-1][y]]=vis[map[x][y]];
    }
    if(map[x][y+1])
    {
        if(map[x][y]>map[x][y+1]) vis[map[x][y]]=vis[map[x][y+1]];
        else vis[map[x][y+1]]=vis[map[x][y]];
    }
    if(map[x][y-1])
    {
        if(map[x][y]>map[x][y-1]) vis[map[x][y]]=vis[map[x][y-1]];
        else vis[map[x][y-1]]=vis[map[x][y]];
    }
}
 
void solve(int time)
{
    int x,y,a;
    int i;
 
    int check=1;
    for(i=1;i<=civ;i++) if(vis[i]!=1) check=0;
    if(check) {printf("%d",time); return ;}
 
    int j=rear;
    while(front!=j)
    {
        x=Q[front][0]; y=Q[front++][1]; a=map[x][y];
        if(extend(a,x+1,y)) find(x+1,y);
        if(extend(a,x-1,y)) find(x-1,y);
        if(extend(a,x,y+1)) find(x,y+1);
        if(extend(a,x,y-1)) find(x,y-1);
    }
 
    for(i=1;i<=civ;i++) if(vis[i]==vis[vis[i]]) {vis[i]=vis[vis[i]];}
    solve(time+1);
}
 
int main()
{
    int i;
    scanf("%d %d",&map_size,&civ);
    for(i=1;i<=civ;i++) vis[i]=i;
 
    for(i=1;i<=civ;i++)
    {
        scanf("%d %d",&start[i][0],&start[i][1]);
        map[start[i][0]][start[i][1]]=i;
        Q[rear][0]=start[i][0]; Q[rear++][1]=start[i][1];
        find(start[i][0],start[i][1]);
    }
    solve(0);
    return 0;
}

Compilation message

civilization.cpp: In function 'int main()':
civilization.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&map_size,&civ);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
civilization.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&start[i][0],&start[i][1]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 760 KB Output is correct
2 Incorrect 3 ms 760 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 760 KB Output is correct
2 Incorrect 3 ms 760 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 760 KB Output is correct
2 Incorrect 3 ms 760 KB Output isn't correct
3 Halted 0 ms 0 KB -