Submission #66415

#TimeUsernameProblemLanguageResultExecution timeMemory
66415ansol4328문명 (KOI17_civilization)C++98
54 / 100
1088 ms55924 KiB
#include<stdio.h> #include<memory.h> #include<queue> using namespace std; int n, k; int visit[2002][2002], num[2002][2002]; struct uf { int p[4000002]; int cnt; bool st[4000002]; void setup(int a) { cnt=a; memset(p,-1,sizeof(p)); memset(st,false,sizeof(st)); } int f(int v) { if(p[v]==-1) return v; p[v]=f(p[v]); return p[v]; } void u(int v1, int v2) // v2 subtree -> v1 subtree { v1=f(v1); v2=f(v2); if(v1==v2) return; if(st[v2]) cnt--; p[v2]=v1; } }; uf T; queue<int> Q; int main() { int c=0; scanf("%d %d",&n,&k); T.setup(k); for(int i=1 ; i<=n ; i++) for(int j=1 ; j<=n ; j++) num[i][j]=++c; for(int i=0 ; i<k ; i++) { int x, y; scanf("%d %d",&y,&x); T.st[num[y][x]]=true; Q.push(y); Q.push(x); visit[y][x]=1; } int res=1; int dy[4]={-1,0,1,0}; int dx[4]={0,1,0,-1}; while(T.cnt!=1) { int y=Q.front(); Q.pop(); int x=Q.front(); Q.pop(); res=max(res,visit[y][x]); for(int i=0 ; i<4 ; i++) { int ny=y+dy[i], nx=x+dx[i]; if(!(ny>=1 && ny<=n && nx>=1 && nx<=n)) continue; if(visit[ny][nx]==0) { visit[ny][nx]=visit[y][x]+1; T.u(num[y][x],num[ny][nx]); Q.push(ny); Q.push(nx); } else if(visit[ny][nx]<visit[y][x]+1) { T.u(num[y][x],num[ny][nx]); res=max(res,visit[y][x]); } if(T.cnt==1) break; } } printf("%d",res-1); return 0; }

Compilation message (stderr)

civilization.cpp: In function 'int main()':
civilization.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~~
civilization.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&y,&x);
         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...