Submission #331773

#TimeUsernameProblemLanguageResultExecution timeMemory
331773daniel920712Dango Maker (JOI18_dango_maker)C++14
33 / 100
261 ms134400 KiB
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <vector> #include <queue> #include <map> #include <set> using namespace std; char all[3005][3005]; vector < int > Next[2][1000005]; vector < pair < int , int > > tt; set < pair < int , int > > vis; bool have[2][1000005]={0}; bool use[2][1000005]={0}; bool is[2][1000005]={0}; int nxt[2][1000005]={0}; int ans=0,a,b; void F(int x,int y) { if(have[x][y]) return ; a++; have[x][y]=1; tt.push_back(make_pair(x,y)); for(auto i:Next[x][y]) F(1-x,i); } bool F2(int x,int y,int fx,int fy,int deg) { if(vis.find(make_pair(x,y))!=vis.end()) return 0; vis.insert(make_pair(x,y)); if(nxt[x][y]==-1&&deg==1) { nxt[x][y]=fy; return 1; } if(deg==1) { if(F2(1-x,nxt[x][y],x,y,1-deg)) { nxt[x][y]=fy; return 1; } } else { for(auto i:Next[x][y]) { if(F2(1-x,i,x,y,1-deg)) { nxt[x][y]=i; return 1; } } } return 0; } int main() { int N,M,i,j; scanf("%d %d",&N,&M); for(i=0;i<N;i++) scanf("%s",all[i]); for(i=0;i<N;i++) for(j=0;j<M-2;j++) if(all[i][j]=='R'&&all[i][j+1]=='G'&&all[i][j+2]=='W') is[0][i*M+j]=1; for(i=0;i<N-2;i++) for(j=0;j<M;j++) if(all[i][j]=='R'&&all[i+1][j]=='G'&&all[i+2][j]=='W') is[1][i*M+j]=1; for(i=0;i<N;i++) { for(j=0;j<M;j++) { if(is[0][i*M+j]&&is[1][i*M+j]) { Next[0][i*M+j].push_back(i*M+j); Next[1][i*M+j].push_back(i*M+j); } if(is[0][i*M+j]&&i>=1&&j+1<M&&is[1][(i-1)*M+j+1]) { Next[0][i*M+j].push_back((i-1)*M+j+1); Next[1][(i-1)*M+j+1].push_back(i*M+j); } if(is[0][i*M+j]&&i>=2&&j+2<M&&is[1][(i-2)*M+j+2]) { Next[0][i*M+j].push_back((i-2)*M+j+2); Next[1][(i-2)*M+j+2].push_back(i*M+j); } } } for(i=0;i<N*M;i++) { if(is[0][i]&&!have[0][i]) { tt.clear(); a=0; F(0,i); ans+=a; for(auto i:tt) nxt[i.first][i.second]=-1; for(auto i:tt) { if(nxt[i.first][i.second]==-1) { vis.clear(); if(F2(i.first,i.second,-1,-1,0)) ans--; } } } if(is[1][i]&&!have[1][i]) { tt.clear(); a=0; F(1,i); ans+=a; for(auto i:tt) nxt[i.first][i.second]=-1; for(auto i:tt) { if(nxt[i.first][i.second]==-1) { vis.clear(); if(F2(i.first,i.second,-1,-1,0)) ans--; } } } } printf("%d\n",ans); //printf("aa\n"); return 0; }

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
dango_maker.cpp:64:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |     for(i=0;i<N;i++) scanf("%s",all[i]);
      |                      ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...