oj.uz

Submission #66410

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

using namespace std;

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

struct uf
{
    int p[4000002];
    int cnt;
    void setup(int a)
    {
        cnt=a;
        memset(p,-1,sizeof(p));
    }
    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;
        p[v2]=v1;
        cnt--;
    }
};

uf T;
queue<int> Q;

int main()
{
    scanf("%d %d",&n,&k);
    T.setup(k);
    for(int i=0 ; i<k ; i++)
    {
        int x, y;
        scanf("%d %d",&y,&x);
        Q.push((y-1)*n+x-1);
        civ[y][x]=(y-1)*n+x-1;
        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()/n+1;
        int x=Q.front()%n+1;
        Q.pop();
        res=max(res,visit[y][x]);
        for(int i=0 ; i<4 ; i++)
        {
            if(!(y+dy[i]>=1 && y+dy[i]<=n && x+dx[i]>=1 && x+dx[i]<=n)) continue;
            if(visit[y+dy[i]][x+dx[i]]==0)
            {
                civ[y+dy[i]][x+dx[i]]=civ[y][x];
                visit[y+dy[i]][x+dx[i]]=visit[y][x]+1;
                Q.push((y+dy[i]-1)*n+x+dx[i]-1);
            }
            else if(visit[y+dy[i]][x+dx[i]]<visit[y][x]+1 && civ[y][x]!=civ[y+dy[i]][x+dx[i]])
            {
                T.u(civ[y][x],civ[y+dy[i]][x+dx[i]]);
                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:40: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:45: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 16 ms 16760 KB Output is correct
2 Correct 16 ms 16760 KB Output is correct
3 Correct 17 ms 16944 KB Output is correct
4 Correct 18 ms 17076 KB Output is correct
5 Correct 17 ms 17076 KB Output is correct
6 Correct 16 ms 17076 KB Output is correct
7 Correct 17 ms 17076 KB Output is correct
8 Correct 17 ms 17076 KB Output is correct
9 Correct 16 ms 17084 KB Output is correct
10 Correct 16 ms 17084 KB Output is correct
11 Correct 17 ms 17128 KB Output is correct
12 Correct 16 ms 17128 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16760 KB Output is correct
2 Correct 16 ms 16760 KB Output is correct
3 Correct 17 ms 16944 KB Output is correct
4 Correct 18 ms 17076 KB Output is correct
5 Correct 17 ms 17076 KB Output is correct
6 Correct 16 ms 17076 KB Output is correct
7 Correct 17 ms 17076 KB Output is correct
8 Correct 17 ms 17076 KB Output is correct
9 Correct 16 ms 17084 KB Output is correct
10 Correct 16 ms 17084 KB Output is correct
11 Correct 17 ms 17128 KB Output is correct
12 Correct 76 ms 31604 KB Output is correct
13 Correct 62 ms 31604 KB Output is correct
14 Correct 76 ms 31604 KB Output is correct
15 Correct 59 ms 31604 KB Output is correct
16 Correct 25 ms 31604 KB Output is correct
17 Correct 364 ms 33392 KB Output is correct
18 Correct 346 ms 33400 KB Output is correct
19 Correct 343 ms 33424 KB Output is correct
20 Correct 348 ms 33424 KB Output is correct
21 Correct 351 ms 33424 KB Output is correct
22 Correct 15 ms 33424 KB Output is correct
23 Correct 71 ms 33424 KB Output is correct
24 Correct 16 ms 17128 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16760 KB Output is correct
2 Correct 16 ms 16760 KB Output is correct
3 Correct 17 ms 16944 KB Output is correct
4 Correct 18 ms 17076 KB Output is correct
5 Correct 17 ms 17076 KB Output is correct
6 Correct 16 ms 17076 KB Output is correct
7 Correct 17 ms 17076 KB Output is correct
8 Correct 17 ms 17076 KB Output is correct
9 Correct 16 ms 17084 KB Output is correct
10 Correct 16 ms 17084 KB Output is correct
11 Correct 17 ms 17128 KB Output is correct
12 Correct 76 ms 31604 KB Output is correct
13 Correct 62 ms 31604 KB Output is correct
14 Correct 76 ms 31604 KB Output is correct
15 Correct 59 ms 31604 KB Output is correct
16 Correct 25 ms 31604 KB Output is correct
17 Correct 364 ms 33392 KB Output is correct
18 Correct 346 ms 33400 KB Output is correct
19 Correct 343 ms 33424 KB Output is correct
20 Correct 348 ms 33424 KB Output is correct
21 Correct 351 ms 33424 KB Output is correct
22 Correct 15 ms 33424 KB Output is correct
23 Correct 71 ms 33424 KB Output is correct
24 Correct 182 ms 46648 KB Output is correct
25 Correct 230 ms 47608 KB Output is correct
26 Correct 160 ms 47608 KB Output is correct
27 Correct 181 ms 47608 KB Output is correct
28 Correct 120 ms 47608 KB Output is correct
29 Correct 844 ms 49868 KB Output is correct
30 Correct 749 ms 49868 KB Output is correct
31 Execution timed out 1002 ms 50796 KB Time limit exceeded
32 Halted 0 ms 0 KB -