Submission #85957

#	Time	Username	Problem	Language	Result	Execution time	Memory
85957		tjdgus4384	문명 (KOI17_civilization)	C++14	19 / 100	1069 ms	23008 KiB

civilization

#include<cstdio>
#include<vector>
#include<string.h>
using namespace std;
int world[2001][2001];
int chk[2001][2001];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
vector<pair<int, int> > v;

void dfs(int x, int y)
{
    chk[x][y] = 1;
    for(int i = 0;i < 4;i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(!chk[nx][ny] && world[nx][ny]) dfs(nx, ny);
    }
}

int main()
{
    int n, k, x, y;
    scanf("%d %d", &n, &k);
    for(int i = 0;i < k;i++)
    {
        scanf("%d %d", &x, &y);
        v.push_back({x, y});
        world[x][y] = 1;
    }
    int ans = 0;
    while(1)
    {
        memset(chk, 0, sizeof(chk));
        dfs(v[0].first, v[0].second);
        bool all = false;
        for(int i = 1;i < v.size();i++)
        {
            if(chk[v[i].first][v[i].second] == 0) {all = true;break;}
        }
        if(!all)
        {
            printf("%d", ans);
            return 0;
        }
        memset(chk, 0, sizeof(chk));
        for(int i = 1;i <= n;i++)
        {
            for(int j = 1;j <= n;j++)
            {
                if(world[i][j] == 1 && !chk[i][j])
                {
                    for(int l = 0;l < 4;l++)
                    {
                        if(!world[i + dx[l]][j + dy[l]])
                        {
                            world[i + dx[l]][j + dy[l]] = 1;
                            chk[i + dx[l]][j + dy[l]] = 1;
                        }
                    }
                }
            }
        }
        ans++;
    }
}

Compilation message (stderr)

civilization.cpp: In function 'int main()':
civilization.cpp:38:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 1;i < v.size();i++)
                       ~~^~~~~~~~~~
civilization.cpp:25: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:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~~

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