Submission #85984

#	Time	Username	Problem	Language	Result	Execution time	Memory
85984		tjdgus4384	문명 (KOI17_civilization)	C++14	100 / 100	922 ms	43716 KiB

civilization

#include<cstdio>
#include<string.h>
#include<queue>
using namespace std;
queue<pair<pair<int, int>, pair<int, int> > > q;
int pa[100001], sz[100001], rk[100001], ar[2001][2001];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int find(int u)
{
    if(pa[u] == u) return u;
    return pa[u] = find(pa[u]);
}

void merge(int u, int v)
{
    u = find(u); v = find(v);
    if(u == v) return;
    if(rk[u] > rk[v]) swap(u, v);
    pa[u] = v;
    sz[v] += sz[u];
    if(rk[u] == rk[v]) rk[v]++;
}

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    for(int i = 1;i <= k;i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        q.push({{x, y}, {i, 0}});
        pa[i] = i;
        rk[i] = 1;
        sz[i] = 1;
    }
    while(!q.empty())
    {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int s = q.front().second.first;
        int t = q.front().second.second;
        q.pop();
        if(ar[x][y] == 0)
        {
            ar[x][y] = s;
            for(int i = 0;i < 4;i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx < 1 || nx > n || ny < 1 || ny > n) continue;
                if(ar[nx][ny] == 0) q.push({{nx, ny}, {s, t + 1}});
                else merge(ar[nx][ny], s);
            }
        }
        else
        {
            merge(ar[x][y], s);
        }
        if(sz[find(1)] == k)
        {
            printf("%d", t);
            return 0;
        }
    }
}

Compilation message (stderr)

civilization.cpp: In function 'int main()':
civilization.cpp:29: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:33: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: 35 / 35
• Subtask 3: 46 / 46