oj.uz

Submission #109311

# Submission time Handle Problem Language Result Execution time Memory
109311 2019-05-06T06:40:35 Z aer0park None (KOI17_civilization) C++14
54 / 100
 1000 ms 104012 KB 
#include <bits/stdc++.h>
#define f first
#define s second
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pi;
 
ll n,k,p[4000004],transp[2004][2004],cnt,coj,anw,vis[4000004];
bool ck[4000004];
ll dx[]={1,0,-1,0},dy[]={0,1,0,-1};
vector<pi> ar;
queue<pi> q;
 
ll par(int a)
{
    if(p[a]==a)
        return a;
    return p[a]=par(p[a]);
}
 
bool merge(ll a,ll b)    
{
    a=par(a),b=par(b);
    if(a!=b)
    {
        p[a]=b;
        return 1;   
    }
    return 0;
}
 
int main() 
{
    scanf("%lld%lld",&n,&k);
    for(int i=0;i<k;i++)
    {
        ll a,b;scanf("%lld%lld",&a,&b);
        ar.push_back({a,b});
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            transp[i][j]=++cnt;
    for(int i=1;i<=n*n;i++)
        p[i]=i,vis[i]=-1;
    for(int i=0;i<k;i++)
    {
    	q.push(ar[i]);
    	vis[transp[ar[i].f][ar[i].s]]=0;
	}
    while(1)
    {
        while(!q.empty())
        {
            ll nwx=q.front().f,nwy=q.front().s;
            if(vis[transp[nwx][nwy]]!=anw)
            	break;
            q.pop();
            coj++;
            for(int i=0;i<4;i++)
            {
                ll ntx=nwx+dx[i],nty=nwy+dy[i];     
                if(ntx<1||ntx>n||nty<1||nty>n)
                    continue;
                if(vis[transp[ntx][nty]]==-1)
                	q.push({ntx,nty}),vis[transp[ntx][nty]]=anw+1;
				else if(vis[transp[ntx][nty]]<=anw)
                {
                    if(merge(transp[nwx][nwy],transp[ntx][nty]))
                		coj--;  
                }    	  
            }
        }
        if(coj==1)
        {
        	printf("%d",anw); 
            break;
        }
        anw++;
    }
    return 0;
}

Compilation message

civilization.cpp: In function 'int main()':
civilization.cpp:77:25: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
          printf("%d",anw); 
                         ^
civilization.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~
civilization.cpp:39:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         ll a,b;scanf("%lld%lld",&a,&b);
                ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1024 KB Output is correct
2 Correct 4 ms 1024 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 4 ms 1024 KB Output is correct
7 Correct 4 ms 996 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 3 ms 1024 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 4 ms 1024 KB Output is correct
12 Correct 3 ms 1024 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1024 KB Output is correct
2 Correct 4 ms 1024 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 4 ms 1024 KB Output is correct
7 Correct 4 ms 996 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 3 ms 1024 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 4 ms 1024 KB Output is correct
12 Correct 117 ms 27912 KB Output is correct
13 Correct 93 ms 27880 KB Output is correct
14 Correct 127 ms 28024 KB Output is correct
15 Correct 91 ms 27896 KB Output is correct
16 Correct 38 ms 27896 KB Output is correct
17 Correct 584 ms 35464 KB Output is correct
18 Correct 660 ms 35400 KB Output is correct
19 Correct 640 ms 35396 KB Output is correct
20 Correct 649 ms 35376 KB Output is correct
21 Correct 645 ms 35432 KB Output is correct
22 Correct 24 ms 27896 KB Output is correct
23 Correct 80 ms 28016 KB Output is correct
24 Correct 3 ms 1024 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1024 KB Output is correct
2 Correct 4 ms 1024 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 4 ms 1024 KB Output is correct
7 Correct 4 ms 996 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 3 ms 1024 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 4 ms 1024 KB Output is correct
12 Correct 117 ms 27912 KB Output is correct
13 Correct 93 ms 27880 KB Output is correct
14 Correct 127 ms 28024 KB Output is correct
15 Correct 91 ms 27896 KB Output is correct
16 Correct 38 ms 27896 KB Output is correct
17 Correct 584 ms 35464 KB Output is correct
18 Correct 660 ms 35400 KB Output is correct
19 Correct 640 ms 35396 KB Output is correct
20 Correct 649 ms 35376 KB Output is correct
21 Correct 645 ms 35432 KB Output is correct
22 Correct 24 ms 27896 KB Output is correct
23 Correct 80 ms 28016 KB Output is correct
24 Correct 380 ms 94452 KB Output is correct
25 Correct 468 ms 94516 KB Output is correct
26 Correct 316 ms 94564 KB Output is correct
27 Correct 348 ms 94456 KB Output is correct
28 Correct 250 ms 94448 KB Output is correct
29 Execution timed out 1072 ms 104012 KB Time limit exceeded
30 Halted 0 ms 0 KB -