Submission #55662

#	Time	Username	Problem	Language	Result	Execution time	Memory
55662		red1108	문명 (KOI17_civilization)	C++17	100 / 100	600 ms	30136 KiB

civilization

#include <iostream>
#include <utility>
#include <queue>
using namespace std;
typedef pair<int,int> P;
#define x first
#define y second
P t;
queue<P> q;
int table[2010][2010],ans=0,cnt,n,k;
int parent[100010];
int par(int a)
{
    if(parent[a]==a) return a;
    return parent[a]=par(parent[a]);
}
void uni(int a, int b)
{
    if(par(a)!=par(b))
    {
        parent[par(a)]=par(b);
        cnt--;
    }
}
bool ch(int a, int b)
{
    if(a<1||b<1||a>n||b>n) return 0;
    return 1;
}
void view(int a, int b)
{
        if(table[a-1][b]) uni(table[a-1][b],table[a][b]);
        if(table[a+1][b]) uni(table[a+1][b],table[a][b]);
        if(table[a][b+1]) uni(table[a][b+1],table[a][b]);
        if(table[a][b-1]) uni(table[a][b-1],table[a][b]);
}
int main()
{
    int i, j,a,b,si;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(i=1;i<=k;i++)
    {
        cin>>a>>b;
        table[a][b]=i;
        parent[i]=i;
        cnt++;
        if(table[a-1][b]) uni(table[a-1][b],table[a][b]);
        if(table[a+1][b]) uni(table[a+1][b],table[a][b]);
        if(table[a][b+1]) uni(table[a][b+1],table[a][b]);
        if(table[a][b-1]) uni(table[a][b-1],table[a][b]);
        q.push({a,b});
    }
    if(cnt==1)
    {
        cout<<0;
        return 0;
    }
    while(!q.empty())
    {
        ans++;
        si=q.size();
        for(i=1;i<=si;i++) {
            a=q.front().x;
            b=q.front().y;
            q.pop();
            if(table[a+1][b]==0&&ch(a+1,b)){table[a+1][b]=par(table[a][b]);q.push({a+1,b});view(a+1,b);}
            if(table[a-1][b]==0&&ch(a-1,b)){table[a-1][b]=par(table[a][b]);q.push({a-1,b});view(a-1,b);}
            if(table[a][b+1]==0&&ch(a,b+1)){table[a][b+1]=par(table[a][b]);q.push({a,b+1});view(a,b+1);}
            if(table[a][b-1]==0&&ch(a,b-1)){table[a][b-1]=par(table[a][b]);q.push({a,b-1});view(a,b-1);}
        }
        if(cnt==1)
        {
            cout<<ans;
            return 0;
        }
    }
}

Compilation message (stderr)

civilization.cpp: In function 'int main()':
civilization.cpp:39:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j,a,b,si;
            ^

• Subtask 1: 19 / 19
• Subtask 2: 35 / 35
• Subtask 3: 46 / 46