Submission #124474

#	Time	Username	Problem	Language	Result	Execution time	Memory
124474		DJ035	문명 (KOI17_civilization)	C++14	100 / 100	892 ms	40068 KiB

civilization

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,par[101010],sz[101010],chk[2020][2020],day[2020][2020],dx[4]={0,0,1,-1},dy[4]={-1,1,0,0},cnt,a,b;
queue<int> qx,qy;
int f(int a){
    if(a==par[a]) return a;
    return par[a]=f(par[a]);
}
void uni(int a,int b){
    if(sz[a]>=sz[b]) par[b]=a,sz[a]+=sz[b];
    else par[a]=b,sz[b]+=sz[a];
}
main(){
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        cin >> a >> b;
        par[i]=chk[a][b]=i;
        qx.push(a),qy.push(b);
    }
    if(m==1){cout << 0;return 0;}
    while(!qx.empty()){
        int x=qx.front(),y=qy.front();
        qx.pop(),qy.pop();
        for(int i=0;i<4;i++){
            int xx=x+dx[i],yy=y+dy[i];
            if(xx<1 || yy<1 || xx>n || yy>n) continue;
            if(chk[xx][yy]){
                if(day[xx][yy] <= day[x][y] && f(chk[x][y]) != f(chk[xx][yy])){
                    uni(f(chk[x][y]),f(chk[xx][yy]));
                    cnt++;
                    if(cnt == m-1){cout << day[x][y];return 0;}
                }
                continue;
            }
            qx.push(xx),qy.push(yy);
            chk[xx][yy]=chk[x][y];
            day[xx][yy]=day[x][y]+1;
        }
    }
}

Compilation message (stderr)

civilization.cpp:14:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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