oj.uz

Submission #109305

# Submission time Handle Problem Language Result Execution time Memory
109305 2019-05-06T06:35:41 Z aer0park None (KOI17_civilization) C++14
54 / 100
 1000 ms 104440 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,wq;
 
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++)
    {
    	wq.push(ar[i]);
    	vis[transp[ar[i].f][ar[i].s]]=0;
	}
    while(1)
    {
        while(!wq.empty())
        {
            pi a=wq.front();
            q.push(a);
            wq.pop();
        }
        while(!q.empty())
        {
            ll nwx=q.front().f,nwy=q.front().s;
            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)
                	wq.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 4 ms 1024 KB Output is correct
2 Correct 3 ms 1024 KB Output is correct
3 Correct 2 ms 1024 KB Output is correct
4 Correct 4 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 1024 KB Output is correct
8 Correct 4 ms 896 KB Output is correct
9 Correct 4 ms 1052 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 4 ms 1024 KB Output is correct
2 Correct 3 ms 1024 KB Output is correct
3 Correct 2 ms 1024 KB Output is correct
4 Correct 4 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 1024 KB Output is correct
8 Correct 4 ms 896 KB Output is correct
9 Correct 4 ms 1052 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 4 ms 1024 KB Output is correct
12 Correct 130 ms 27944 KB Output is correct
13 Correct 99 ms 27904 KB Output is correct
14 Correct 131 ms 28024 KB Output is correct
15 Correct 104 ms 27904 KB Output is correct
16 Correct 34 ms 27904 KB Output is correct
17 Correct 623 ms 35432 KB Output is correct
18 Correct 674 ms 35604 KB Output is correct
19 Correct 745 ms 35560 KB Output is correct
20 Correct 655 ms 35688 KB Output is correct
21 Correct 617 ms 35432 KB Output is correct
22 Correct 25 ms 27896 KB Output is correct
23 Correct 83 ms 27900 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 4 ms 1024 KB Output is correct
2 Correct 3 ms 1024 KB Output is correct
3 Correct 2 ms 1024 KB Output is correct
4 Correct 4 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 1024 KB Output is correct
8 Correct 4 ms 896 KB Output is correct
9 Correct 4 ms 1052 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 4 ms 1024 KB Output is correct
12 Correct 130 ms 27944 KB Output is correct
13 Correct 99 ms 27904 KB Output is correct
14 Correct 131 ms 28024 KB Output is correct
15 Correct 104 ms 27904 KB Output is correct
16 Correct 34 ms 27904 KB Output is correct
17 Correct 623 ms 35432 KB Output is correct
18 Correct 674 ms 35604 KB Output is correct
19 Correct 745 ms 35560 KB Output is correct
20 Correct 655 ms 35688 KB Output is correct
21 Correct 617 ms 35432 KB Output is correct
22 Correct 25 ms 27896 KB Output is correct
23 Correct 83 ms 27900 KB Output is correct
24 Correct 362 ms 94580 KB Output is correct
25 Correct 515 ms 94620 KB Output is correct
26 Correct 337 ms 94460 KB Output is correct
27 Correct 393 ms 94584 KB Output is correct
28 Correct 264 ms 94584 KB Output is correct
29 Execution timed out 1078 ms 104440 KB Time limit exceeded
30 Halted 0 ms 0 KB -