oj.uz

Submission #59104

# Submission time Handle Problem Language Result Execution time Memory
59104 2018-07-20T14:37:22 Z andy627 None (KOI17_civilization) C++17
54 / 100
 1000 ms 64324 KB 
#include <stdio.h>
#include <queue>
#include <algorithm>
#define INF 2e9
using namespace std;

int par[2222*2222];
int dist[2222][2222],num[2222][2222];
bool is_gone[2222][2222];
queue<int> qx,qy;

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

int find_(int x){
    if(par[x]==x) return x;
    return par[x]=find_(par[x]);
}

int main(){
    int n,k;

    scanf("%d %d",&n,&k);

    int pos=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) dist[i][j]=INF,num[i][j]=++pos;
    for(int i=1;i<=pos;i++) par[i]=i;

    for(int i=1;i<=k;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        dist[a][b]=0;
        qx.push(a); qy.push(b);
    }

    int ans=0,cnt=0;
    for(;;ans++){
        while(!qx.empty()){
            int px=qx.front(); qx.pop();
            int py=qy.front(); qy.pop();

            if(dist[px][py]!=ans){
                qx.push(px); qy.push(py);
                break;
            }

            is_gone[px][py]=1; cnt++;
            for(int d=0;d<4;d++){
                int nx=px+dx[d];
                int ny=py+dy[d];

                if(nx<1 || nx>n || ny<1 || ny>n) continue;
                if(is_gone[nx][ny]){
                    int root_a=find_(num[nx][ny]);
                    int root_b=find_(num[px][py]);

                    if(root_a!=root_b) cnt--;
                    par[root_b]=root_a;
                }
                else if(dist[nx][ny]==INF){
                    dist[nx][ny]=dist[px][py]+1;
                    qx.push(nx); qy.push(ny);
                }
            }
        }
        if(cnt==1) break;
    }

    printf("%d\n",ans);

    return 0;
}

Compilation message

civilization.cpp: In function 'int main()':
civilization.cpp:23: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:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Correct 4 ms 1540 KB Output is correct
3 Correct 4 ms 1560 KB Output is correct
4 Correct 4 ms 1672 KB Output is correct
5 Correct 5 ms 1676 KB Output is correct
6 Correct 6 ms 1736 KB Output is correct
7 Correct 4 ms 1848 KB Output is correct
8 Correct 3 ms 1852 KB Output is correct
9 Correct 5 ms 1856 KB Output is correct
10 Correct 4 ms 1856 KB Output is correct
11 Correct 4 ms 1860 KB Output is correct
12 Correct 5 ms 1980 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Correct 4 ms 1540 KB Output is correct
3 Correct 4 ms 1560 KB Output is correct
4 Correct 4 ms 1672 KB Output is correct
5 Correct 5 ms 1676 KB Output is correct
6 Correct 6 ms 1736 KB Output is correct
7 Correct 4 ms 1848 KB Output is correct
8 Correct 3 ms 1852 KB Output is correct
9 Correct 5 ms 1856 KB Output is correct
10 Correct 4 ms 1856 KB Output is correct
11 Correct 4 ms 1860 KB Output is correct
12 Correct 156 ms 22908 KB Output is correct
13 Correct 117 ms 22908 KB Output is correct
14 Correct 150 ms 22908 KB Output is correct
15 Correct 101 ms 22908 KB Output is correct
16 Correct 38 ms 22908 KB Output is correct
17 Correct 561 ms 26432 KB Output is correct
18 Correct 548 ms 27304 KB Output is correct
19 Correct 503 ms 27944 KB Output is correct
20 Correct 530 ms 28864 KB Output is correct
21 Correct 452 ms 29616 KB Output is correct
22 Correct 19 ms 29616 KB Output is correct
23 Correct 66 ms 29616 KB Output is correct
24 Correct 5 ms 1980 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Correct 4 ms 1540 KB Output is correct
3 Correct 4 ms 1560 KB Output is correct
4 Correct 4 ms 1672 KB Output is correct
5 Correct 5 ms 1676 KB Output is correct
6 Correct 6 ms 1736 KB Output is correct
7 Correct 4 ms 1848 KB Output is correct
8 Correct 3 ms 1852 KB Output is correct
9 Correct 5 ms 1856 KB Output is correct
10 Correct 4 ms 1856 KB Output is correct
11 Correct 4 ms 1860 KB Output is correct
12 Correct 156 ms 22908 KB Output is correct
13 Correct 117 ms 22908 KB Output is correct
14 Correct 150 ms 22908 KB Output is correct
15 Correct 101 ms 22908 KB Output is correct
16 Correct 38 ms 22908 KB Output is correct
17 Correct 561 ms 26432 KB Output is correct
18 Correct 548 ms 27304 KB Output is correct
19 Correct 503 ms 27944 KB Output is correct
20 Correct 530 ms 28864 KB Output is correct
21 Correct 452 ms 29616 KB Output is correct
22 Correct 19 ms 29616 KB Output is correct
23 Correct 66 ms 29616 KB Output is correct
24 Correct 387 ms 59584 KB Output is correct
25 Correct 459 ms 59592 KB Output is correct
26 Correct 315 ms 59592 KB Output is correct
27 Correct 435 ms 59592 KB Output is correct
28 Correct 251 ms 59592 KB Output is correct
29 Execution timed out 1092 ms 64324 KB Time limit exceeded
30 Halted 0 ms 0 KB -