oj.uz

Submission #66415

# Submission time Handle Problem Language Result Execution time Memory
66415 2018-08-10T12:46:53 Z ansol4328 None (KOI17_civilization) C++
54 / 100
 1000 ms 55924 KB 
#include<stdio.h>
#include<memory.h>
#include<queue>

using namespace std;

int n, k;
int visit[2002][2002], num[2002][2002];

struct uf
{
    int p[4000002];
    int cnt;
    bool st[4000002];
    void setup(int a)
    {
        cnt=a;
        memset(p,-1,sizeof(p));
        memset(st,false,sizeof(st));
    }
    int f(int v)
    {
        if(p[v]==-1) return v;
        p[v]=f(p[v]);
        return p[v];
    }
    void u(int v1, int v2) // v2 subtree -> v1 subtree
    {
        v1=f(v1);
        v2=f(v2);
        if(v1==v2) return;
        if(st[v2]) cnt--;
        p[v2]=v1;
    }
};

uf T;
queue<int> Q;

int main()
{
    int c=0;
    scanf("%d %d",&n,&k);
    T.setup(k);
    for(int i=1 ; i<=n ; i++) for(int j=1 ; j<=n ; j++) num[i][j]=++c;
    for(int i=0 ; i<k ; i++)
    {
        int x, y;
        scanf("%d %d",&y,&x);
        T.st[num[y][x]]=true;
        Q.push(y);
        Q.push(x);
        visit[y][x]=1;
    }
    int res=1;
    int dy[4]={-1,0,1,0};
    int dx[4]={0,1,0,-1};
    while(T.cnt!=1)
    {
        int y=Q.front(); Q.pop();
        int x=Q.front(); Q.pop();
        res=max(res,visit[y][x]);
        for(int i=0 ; i<4 ; i++)
        {
            int ny=y+dy[i], nx=x+dx[i];
            if(!(ny>=1 && ny<=n && nx>=1 && nx<=n)) continue;
            if(visit[ny][nx]==0)
            {
                visit[ny][nx]=visit[y][x]+1;
                T.u(num[y][x],num[ny][nx]);
                Q.push(ny);
                Q.push(nx);
            }
            else if(visit[ny][nx]<visit[y][x]+1)
            {
                T.u(num[y][x],num[ny][nx]);
                res=max(res,visit[y][x]);
            }
            if(T.cnt==1) break;
        }
    }
    printf("%d",res-1);
    return 0;
}

Compilation message

civilization.cpp: In function 'int main()':
civilization.cpp:43: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:49: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 17 ms 20728 KB Output is correct
2 Correct 17 ms 20728 KB Output is correct
3 Correct 19 ms 20896 KB Output is correct
4 Correct 19 ms 20896 KB Output is correct
5 Correct 17 ms 20896 KB Output is correct
6 Correct 20 ms 20948 KB Output is correct
7 Correct 21 ms 20948 KB Output is correct
8 Correct 23 ms 21024 KB Output is correct
9 Correct 17 ms 21052 KB Output is correct
10 Correct 17 ms 21052 KB Output is correct
11 Correct 18 ms 21052 KB Output is correct
12 Correct 20 ms 21052 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 20728 KB Output is correct
2 Correct 17 ms 20728 KB Output is correct
3 Correct 19 ms 20896 KB Output is correct
4 Correct 19 ms 20896 KB Output is correct
5 Correct 17 ms 20896 KB Output is correct
6 Correct 20 ms 20948 KB Output is correct
7 Correct 21 ms 20948 KB Output is correct
8 Correct 23 ms 21024 KB Output is correct
9 Correct 17 ms 21052 KB Output is correct
10 Correct 17 ms 21052 KB Output is correct
11 Correct 18 ms 21052 KB Output is correct
12 Correct 117 ms 35688 KB Output is correct
13 Correct 103 ms 35688 KB Output is correct
14 Correct 129 ms 35688 KB Output is correct
15 Correct 87 ms 35688 KB Output is correct
16 Correct 31 ms 35688 KB Output is correct
17 Correct 442 ms 38896 KB Output is correct
18 Correct 509 ms 38896 KB Output is correct
19 Correct 494 ms 38976 KB Output is correct
20 Correct 491 ms 38976 KB Output is correct
21 Correct 539 ms 38984 KB Output is correct
22 Correct 22 ms 38984 KB Output is correct
23 Correct 71 ms 38984 KB Output is correct
24 Correct 20 ms 21052 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 20728 KB Output is correct
2 Correct 17 ms 20728 KB Output is correct
3 Correct 19 ms 20896 KB Output is correct
4 Correct 19 ms 20896 KB Output is correct
5 Correct 17 ms 20896 KB Output is correct
6 Correct 20 ms 20948 KB Output is correct
7 Correct 21 ms 20948 KB Output is correct
8 Correct 23 ms 21024 KB Output is correct
9 Correct 17 ms 21052 KB Output is correct
10 Correct 17 ms 21052 KB Output is correct
11 Correct 18 ms 21052 KB Output is correct
12 Correct 117 ms 35688 KB Output is correct
13 Correct 103 ms 35688 KB Output is correct
14 Correct 129 ms 35688 KB Output is correct
15 Correct 87 ms 35688 KB Output is correct
16 Correct 31 ms 35688 KB Output is correct
17 Correct 442 ms 38896 KB Output is correct
18 Correct 509 ms 38896 KB Output is correct
19 Correct 494 ms 38976 KB Output is correct
20 Correct 491 ms 38976 KB Output is correct
21 Correct 539 ms 38984 KB Output is correct
22 Correct 22 ms 38984 KB Output is correct
23 Correct 71 ms 38984 KB Output is correct
24 Correct 350 ms 51204 KB Output is correct
25 Correct 380 ms 51636 KB Output is correct
26 Correct 259 ms 51636 KB Output is correct
27 Correct 319 ms 51636 KB Output is correct
28 Correct 226 ms 51636 KB Output is correct
29 Execution timed out 1088 ms 55924 KB Time limit exceeded
30 Halted 0 ms 0 KB -