Submission #394829

#	Time	Username	Problem	Language	Result	Execution time	Memory
394829		jk410	문명 (KOI17_civilization)	C++17	100 / 100	813 ms	24392 KiB

civilization

#include <bits/stdc++.h>
using namespace std;
struct point{
    int x,y;
};
int N,K,cnt;
int A[2001][2001],Par[100001],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
point Point[100001];
queue<point> Q;
int getpar(int v){
    if (v==Par[v])
        return v;
    return Par[v]=getpar(Par[v]);
}
void unite(int a,int b){
    a=getpar(a);
    b=getpar(b);
    if (a!=b){
        Par[b]=a;
        cnt--;
    }
}
bool f(int x,int y){
    return 0<x&&x<=N&&0<y&&y<=N;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>K;
    cnt=K;
    for (int i=1; i<=K; i++){
        cin>>Point[i].x>>Point[i].y;
        A[Point[i].x][Point[i].y]=i;
        Q.push({Point[i].x,Point[i].y});
        Par[i]=i;
    }
    for (int ans=0;;ans++){
        int sz=Q.size();
        while (sz--){
            point t=Q.front();
            Q.pop();
            for (int i=0; i<4; i++){
                int x=t.x+dx[i],y=t.y+dy[i];
                if (f(x,y)&&A[x][y]){
                    unite(A[t.x][t.y],A[x][y]);
                    if (cnt==1){
                        cout<<ans;
                        return 0;
                    }
                }
            }
            Q.push(t);
        }
        sz=Q.size();
        while (sz--){
            point t=Q.front();
            Q.pop();
            for (int i=0; i<4; i++){
                int x=t.x+dx[i],y=t.y+dy[i];
                if (f(x,y)&&!A[x][y]){
                    A[x][y]=A[t.x][t.y];
                    Q.push({x,y});
                }
            }
        }
    }
}

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