oj.uz

Submission #148042

# Submission time Handle Problem Language Result Execution time Memory
148042 2019-08-31T12:11:05 Z arnold518 None (KOI17_civilization) C++14
54 / 100
 1000 ms 52444 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;
const int MAXK = 1e5;

const int dy[]={-1, 1, 0, 0};
const int dx[]={0, 0, -1, 1};

int N, K, A[MAXN+10][MAXN+10];

int conv(int y, int x) { return (y-1)*N+(x-1); }

int par[MAXN*MAXN+10], Rank[MAXN*MAXN+10], cnt=0, ans;
int Find(int x) { return x==par[x]?x:par[x]=Find(par[x]); }
void Union(int x, int y)
{
    x=Find(x); y=Find(y);
    if(Rank[x]<Rank[y]) swap(x, y);
    if(Rank[x]==Rank[y]) Rank[x]++;
    par[y]=x;
}


struct Queue { int y, x; };
queue<Queue> Q;

int main()
{
    int i, j, k;

    scanf("%d%d", &N, &K);
    for(i=0; i<N*N; i++) par[i]=i, Rank[i]=1;
    for(i=1; i<=K; i++)
    {
        int y, x;
        scanf("%d%d", &y, &x);
        A[y][x]=1;
        Q.push({y, x}); cnt++;
    }

    for(i=1; i<=N; i++) for(j=1; j<=N; j++)
    {
        if(!A[i][j]) continue;
        for(k=0; k<4; k++)
        {
            int ny=i+dy[k], nx=j+dx[k];
            if(!(1<=ny && ny<=N && 1<=nx && nx<=N)) continue;
            if(!A[ny][nx]) continue;
            if(Find(conv(ny, nx))!=Find(conv(i, j)))
            {
                cnt--;
                Union(conv(ny, nx), conv(i, j));
            }
        }
    }

    //for(i=1; i<=N; i++) { for(j=1; j<=N; j++) printf("%d ", A[i][j]); printf("\n"); }
    //printf("\n");

    if(cnt==1) return !printf("0");

    while(!Q.empty())
    {
        int sz=Q.size(); ans++;
        while(sz--)
        {
            Queue T=Q.front(); Q.pop();
            for(i=0; i<4; i++)
            {
                int ny=T.y+dy[i], nx=T.x+dx[i];
                if(!(1<=ny && ny<=N && 1<=nx && nx<=N)) continue;
                if(Find(conv(ny, nx))==Find(conv(T.y, T.x))) continue;
                if(A[ny][nx]==0)
                {
                    Union(conv(ny, nx), conv(T.y, T.x));
                    A[ny][nx]=1;
                    Q.push({ny, nx});
                    for(j=0; j<4; j++)
                    {
                        int nny=ny+dy[j], nnx=nx+dx[j];
                        if(!(1<=nny && nny<=N && 1<=nnx && nnx<=N)) continue;
                        if(Find(conv(ny, nx))==Find(conv(nny, nnx))) continue;
                        if(A[nny][nnx]!=0)
                        {
                            cnt--;
                            Union(conv(ny, nx), conv(nny, nnx));
                        }

                    }
                }
                else
                {
                    cnt--;
                    Union(conv(ny, nx), conv(T.y, T.x));
                }
            }
        }

        //for(i=1; i<=N; i++) { for(j=1; j<=N; j++) printf("%d ", A[i][j]); printf("\n"); }
        //printf("-> %d\n", cnt);
        if(cnt==1) return !printf("%d", ans);
    }
}

Compilation message

civilization.cpp: In function 'int main()':
civilization.cpp:36: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:41: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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 3 ms 884 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 4 ms 888 KB Output is correct
9 Correct 4 ms 888 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Correct 3 ms 888 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 3 ms 884 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 4 ms 888 KB Output is correct
9 Correct 4 ms 888 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Correct 128 ms 16056 KB Output is correct
13 Correct 100 ms 15120 KB Output is correct
14 Correct 132 ms 15684 KB Output is correct
15 Correct 89 ms 14456 KB Output is correct
16 Correct 25 ms 10064 KB Output is correct
17 Correct 278 ms 19744 KB Output is correct
18 Correct 382 ms 19968 KB Output is correct
19 Correct 329 ms 19960 KB Output is correct
20 Correct 310 ms 19868 KB Output is correct
21 Correct 314 ms 19848 KB Output is correct
22 Correct 13 ms 8184 KB Output is correct
23 Correct 104 ms 16120 KB Output is correct
24 Correct 3 ms 888 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 3 ms 884 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 4 ms 888 KB Output is correct
9 Correct 4 ms 888 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Correct 128 ms 16056 KB Output is correct
13 Correct 100 ms 15120 KB Output is correct
14 Correct 132 ms 15684 KB Output is correct
15 Correct 89 ms 14456 KB Output is correct
16 Correct 25 ms 10064 KB Output is correct
17 Correct 278 ms 19744 KB Output is correct
18 Correct 382 ms 19968 KB Output is correct
19 Correct 329 ms 19960 KB Output is correct
20 Correct 310 ms 19868 KB Output is correct
21 Correct 314 ms 19848 KB Output is correct
22 Correct 13 ms 8184 KB Output is correct
23 Correct 104 ms 16120 KB Output is correct
24 Correct 358 ms 46968 KB Output is correct
25 Correct 511 ms 47500 KB Output is correct
26 Correct 320 ms 42744 KB Output is correct
27 Correct 369 ms 47208 KB Output is correct
28 Correct 245 ms 41844 KB Output is correct
29 Execution timed out 1079 ms 52444 KB Time limit exceeded
30 Halted 0 ms 0 KB -