oj.uz

Submission #109310

# Submission time Handle Problem Language Result Execution time Memory
109310 2019-05-06T06:38:20 Z aer0park None (KOI17_civilization) C++14
54 / 100
 1000 ms 104064 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() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>k;
    for(int i=0;i<k;i++)
    {
        ll a,b;cin>>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)
        {
        	cout<<anw; 
            break;
        }
        anw++;
    }
    return 0;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1024 KB Output is correct
2 Correct 3 ms 1024 KB Output is correct
3 Correct 4 ms 1024 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 4 ms 1024 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 4 ms 1024 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 4 ms 1024 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 3 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 3 ms 1024 KB Output is correct
3 Correct 4 ms 1024 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 4 ms 1024 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 4 ms 1024 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 4 ms 1024 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 3 ms 1024 KB Output is correct
12 Correct 128 ms 27936 KB Output is correct
13 Correct 96 ms 27944 KB Output is correct
14 Correct 139 ms 27924 KB Output is correct
15 Correct 92 ms 28024 KB Output is correct
16 Correct 35 ms 27904 KB Output is correct
17 Correct 574 ms 35348 KB Output is correct
18 Correct 639 ms 35664 KB Output is correct
19 Correct 629 ms 35568 KB Output is correct
20 Correct 619 ms 35560 KB Output is correct
21 Correct 633 ms 35400 KB Output is correct
22 Correct 25 ms 27896 KB Output is correct
23 Correct 71 ms 27896 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 3 ms 1024 KB Output is correct
3 Correct 4 ms 1024 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 4 ms 1024 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 4 ms 1024 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 4 ms 1024 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 3 ms 1024 KB Output is correct
12 Correct 128 ms 27936 KB Output is correct
13 Correct 96 ms 27944 KB Output is correct
14 Correct 139 ms 27924 KB Output is correct
15 Correct 92 ms 28024 KB Output is correct
16 Correct 35 ms 27904 KB Output is correct
17 Correct 574 ms 35348 KB Output is correct
18 Correct 639 ms 35664 KB Output is correct
19 Correct 629 ms 35568 KB Output is correct
20 Correct 619 ms 35560 KB Output is correct
21 Correct 633 ms 35400 KB Output is correct
22 Correct 25 ms 27896 KB Output is correct
23 Correct 71 ms 27896 KB Output is correct
24 Correct 380 ms 94548 KB Output is correct
25 Correct 490 ms 94452 KB Output is correct
26 Correct 342 ms 94584 KB Output is correct
27 Correct 382 ms 94468 KB Output is correct
28 Correct 247 ms 94456 KB Output is correct
29 Execution timed out 1078 ms 104064 KB Time limit exceeded
30 Halted 0 ms 0 KB -