oj.uz

Submission #148019

# Submission time Handle Problem Language Result Execution time Memory
148019 2019-08-31T11:17:03 Z arnold518 None (KOI17_civilization) C++14
54 / 100
 1000 ms 52356 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});
                }
                else
                {
                    cnt--;
                    Union(conv(ny, nx), conv(T.y, T.x));
                }
            }
        }

        sz=Q.size();
        while(sz--)
        {
            Queue T=Q.front(); Q.pop(); Q.push(T);
            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)
                {
                    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 888 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 888 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 4 ms 916 KB Output is correct
7 Correct 4 ms 888 KB Output is correct
8 Correct 3 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 888 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 888 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 4 ms 916 KB Output is correct
7 Correct 4 ms 888 KB Output is correct
8 Correct 3 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 144 ms 15888 KB Output is correct
13 Correct 113 ms 15096 KB Output is correct
14 Correct 139 ms 15588 KB Output is correct
15 Correct 93 ms 14456 KB Output is correct
16 Correct 27 ms 10104 KB Output is correct
17 Correct 302 ms 19804 KB Output is correct
18 Correct 400 ms 19832 KB Output is correct
19 Correct 320 ms 19832 KB Output is correct
20 Correct 432 ms 19832 KB Output is correct
21 Correct 329 ms 19832 KB Output is correct
22 Correct 13 ms 8184 KB Output is correct
23 Correct 99 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 888 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 888 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 4 ms 916 KB Output is correct
7 Correct 4 ms 888 KB Output is correct
8 Correct 3 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 144 ms 15888 KB Output is correct
13 Correct 113 ms 15096 KB Output is correct
14 Correct 139 ms 15588 KB Output is correct
15 Correct 93 ms 14456 KB Output is correct
16 Correct 27 ms 10104 KB Output is correct
17 Correct 302 ms 19804 KB Output is correct
18 Correct 400 ms 19832 KB Output is correct
19 Correct 320 ms 19832 KB Output is correct
20 Correct 432 ms 19832 KB Output is correct
21 Correct 329 ms 19832 KB Output is correct
22 Correct 13 ms 8184 KB Output is correct
23 Correct 99 ms 16120 KB Output is correct
24 Correct 396 ms 47060 KB Output is correct
25 Correct 536 ms 47412 KB Output is correct
26 Correct 360 ms 42848 KB Output is correct
27 Correct 382 ms 47224 KB Output is correct
28 Correct 263 ms 41740 KB Output is correct
29 Execution timed out 1078 ms 52356 KB Time limit exceeded
30 Halted 0 ms 0 KB -