제출 #239082

#제출 시각아이디문제언어결과실행 시간메모리
239082urd05무지개나라 (APIO17_rainbow)C++14
11 / 100
85 ms1680 KiB
#include <bits/stdc++.h> using namespace std; char str[100001]; int r,c,sr,sc; int l; int arr[51][200001]; typedef pair<int,int> P; vector<int> st[3]; vector<int> en[3]; vector<int> ts; vector<int> te; void init(int rr,int cc,int srr,int scc,int m,char s[]) { r=rr; c=cc; sr=srr; sc=scc; l=m; for(int i=0;i<m;i++) { str[i]=s[i]; } arr[sr][sc]=1; vector<P> v; int x=sr; int y=sc; v.push_back(P(x,y)); for(int i=0;i<m;i++) { if (str[i]=='W') { y--; } if (str[i]=='E') { y++; } if (str[i]=='N') { x--; } if (str[i]=='S') { x++; } arr[x][y]=1; v.push_back(P(x,y)); } if (r==2) { for(int j=1;j<=2;j++) { bool flag=false; for(int i=1;i<=c;i++) { if (arr[j][i]==0) { if (!flag) { flag=true; st[j].push_back(i); } } if (arr[j][i]==1) { if (flag) { flag=false; en[j].push_back(i-1); } } } if (arr[j][c]==0) { en[j].push_back(c); } } bool flag=false; for(int i=1;i<=c;i++) { if (arr[1][i]==1&&arr[2][i]==1) { if (!flag) { flag=true; ts.push_back(i); } } else { if (flag) { flag=false; te.push_back(i-1); } } } if (arr[1][c]==1&&arr[2][c]==1) { te.push_back(c); } } } struct UnionFind { P p[51][51]; void init() { for(int i=1;i<=r;i++) { for(int j=1;j<=c;j++) { p[i][j]=P(-1,-1); } } } P find(int x,int y) { if (p[x][y]<P(0,0)) { return P(x,y); } p[x][y]=find(p[x][y].first,p[x][y].second); return p[x][y]; } int merge(P a,P b) { a=find(a.first,a.second); b=find(b.first,b.second); if (a==b) { return 0; } p[b.first][b.second]=a; return 1; } }; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; int solve1(int ar,int ac,int br,int bc) { UnionFind uf; uf.init(); int sum=0; for(int i=ar;i<=br;i++) { for(int j=ac;j<=bc;j++) { if (arr[i][j]==0) { sum++; for(int k=0;k<4;k++) { int x=i+dx[k]; int y=j+dy[k]; if (x>=ar&&x<=br&&y>=ac&&y<=bc&&arr[x][y]==0) { sum-=uf.merge(P(i,j),P(x,y)); } } } } } return sum; } int solve2(int ar,int ac,int br,int bc) { if (ar==br) { int fr=lower_bound(en[ar].begin(),en[ar].end(),ac)-en[ar].begin(); int ba=upper_bound(st[ar].begin(),st[ar].end(),bc)-st[ar].begin()-1; int ret=ba-fr+1; return ret; } else { if (ac==bc) { return (arr[ar][ac]==1&&arr[ar][bc]==1)?0:1; } int fr=lower_bound(te.begin(),te.end(),ac)-te.begin(); int ba=upper_bound(ts.begin(),ts.end(),bc)-ts.begin()-1; int ret=ba-fr; if (arr[1][ac]==0||arr[2][ac]==0) { ret++; } if (arr[2][bc]==0||arr[2][bc]==0) { ret++; } return ret; } } int colour(int ar,int ac,int br,int bc) { if (r<=50&&c<=50) { return solve1(ar,ac,br,bc); } if (r==2) { return solve2(ar,ac,br,bc); } }

컴파일 시 표준 에러 (stderr) 메시지

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:168:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...