oj.uz

Submission #148011

# Submission time Handle Problem Language Result Execution time Memory
148011 2019-08-31T11:10:07 Z arnold518 None (KOI17_civilization) C++14
54 / 100
 1000 ms 36600 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], col[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);
    par[x]=y;
}

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

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;
    for(i=1; i<=K; i++)
    {
        int y, x;
        scanf("%d%d", &y, &x);
        A[y][x]=-1;
        Q.push({y, x});
    }

    for(i=1; i<=N; i++) for(j=1; j<=N; j++)
    {
        if(A[i][j]!=-1) continue;
        dfs(i, j);
        cnt++;
    }

    //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 'void dfs(int, int)':
civilization.cpp:28:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
civilization.cpp: In function 'int main()':
civilization.cpp:45:15: warning: unused variable 'k' [-Wunused-variable]
     int i, j, k;
               ^
civilization.cpp:47: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:52: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 632 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 3 ms 760 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 760 KB Output is correct
8 Correct 4 ms 760 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 764 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 632 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 3 ms 760 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 760 KB Output is correct
8 Correct 4 ms 760 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 118 ms 12024 KB Output is correct
13 Correct 92 ms 11184 KB Output is correct
14 Correct 115 ms 11736 KB Output is correct
15 Correct 80 ms 10496 KB Output is correct
16 Correct 19 ms 6264 KB Output is correct
17 Correct 313 ms 15900 KB Output is correct
18 Correct 339 ms 15992 KB Output is correct
19 Correct 397 ms 15864 KB Output is correct
20 Correct 348 ms 15864 KB Output is correct
21 Correct 353 ms 15864 KB Output is correct
22 Correct 9 ms 4472 KB Output is correct
23 Correct 94 ms 12280 KB Output is correct
24 Correct 3 ms 764 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 632 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 3 ms 760 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 760 KB Output is correct
8 Correct 4 ms 760 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 118 ms 12024 KB Output is correct
13 Correct 92 ms 11184 KB Output is correct
14 Correct 115 ms 11736 KB Output is correct
15 Correct 80 ms 10496 KB Output is correct
16 Correct 19 ms 6264 KB Output is correct
17 Correct 313 ms 15900 KB Output is correct
18 Correct 339 ms 15992 KB Output is correct
19 Correct 397 ms 15864 KB Output is correct
20 Correct 348 ms 15864 KB Output is correct
21 Correct 353 ms 15864 KB Output is correct
22 Correct 9 ms 4472 KB Output is correct
23 Correct 94 ms 12280 KB Output is correct
24 Correct 344 ms 31408 KB Output is correct
25 Correct 452 ms 31880 KB Output is correct
26 Correct 292 ms 27172 KB Output is correct
27 Correct 349 ms 31464 KB Output is correct
28 Correct 220 ms 26104 KB Output is correct
29 Execution timed out 1081 ms 36600 KB Time limit exceeded
30 Halted 0 ms 0 KB -