Submission #204462

#	Time	Username	Problem	Language	Result	Execution time	Memory
204462		14kg	문명 (KOI17_civilization)	C++11	54 / 100	1004 ms	39992 KiB

civilization

#include <stdio.h>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>
#define max2(x,y) (x>y?x:y)

using namespace std;
typedef pair<int,pair<int,int> > pip;
int n, m, p[100001], max_t;
int dy[4]={1,-1,0,0}, dx[4]={0,0,1,-1};
pair<int,int> board[2001][2001];
queue<int> Q;
priority_queue<pip,vector<pip>,greater<pip> > Q2;

int get_p(int x){
    if(p[x]==x) return x;
    return p[x]=get_p(p[x]);
}
int main(){
    int x, y, xx, yy, tx, ty;

    scanf("%d %d",&n,&m);
    for(int i=1; i<=m; i++){
        scanf("%d %d",&x,&y);
        board[x][y]={i,0}, p[i]=i;
        Q.push(x), Q.push(y);
    }

    while(!Q.empty()){
        xx=Q.front(), Q.pop();
        yy=Q.front(), Q.pop();

        while(Q2.empty()==false && Q2.top().first<=board[xx][yy].second){
            int px=get_p(Q2.top().second.first);
            int py=get_p(Q2.top().second.second);
            if(px!=py) p[px]=py, max_t=max2(max_t,Q2.top().first);
            Q2.pop();
        }

        for(int i=0; i<4; i++){
            tx=xx+dx[i], ty=yy+dy[i];
            if(1<=tx && tx<=n && 1<=ty && ty<=n){
                if(board[tx][ty].first==0){
                    board[tx][ty]={board[xx][yy].first,board[xx][yy].second+1};
                    Q.push(tx), Q.push(ty);
                }

                int px=get_p(board[tx][ty].first);
                int py=get_p(board[xx][yy].first);
                if(px!=py) Q2.push({board[tx][ty].second,{px,py}});
            }
        }
    }
    while(!Q2.empty()){
        int px=get_p(Q2.top().second.first);
        int py=get_p(Q2.top().second.second);
        if(px!=py) p[px]=py, max_t=max2(max_t,Q2.top().first);
        Q2.pop();
    } printf("%d",max_t);
}

Compilation message (stderr)

civilization.cpp: In function 'int main()':
civilization.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~
civilization.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~

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