제출 #729449

#제출 시각아이디문제언어결과실행 시간메모리
729449pccDango Maker (JOI18_dango_maker)C++14
100 / 100
1967 ms21088 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define fs first #define sc second #define _all(a) a.begin(),a.end() #define pii pair<int,int> const int mxn = 3030; struct Edge{ int to; int cap; Edge(){} Edge(int tt,int cc){ to = tt,cap = cc; } }; vector<Edge> edges; bitset<mxn> done[mxn]; vector<vector<int>> paths; vector<int> level; string s[mxn]; int st,ed; void addedge(int a,int b){ paths[a].push_back(edges.size()); edges.push_back(Edge(b,1)); paths[b].push_back(edges.size()); edges.push_back(Edge(a,0)); } bool bfs(){ queue<int> q; fill(level.begin(),level.end(),-1); level[0] = 0; q.push(0); while(!q.empty()){ auto now = q.front(); q.pop(); for(auto &id:paths[now]){ if(!edges[id].cap)continue; auto nxt = edges[id].to; if(level[nxt] == -1){ level[nxt] = level[now]+1; q.push(nxt); } } } return level[ed] != -1; } int dfs(int now,int lim){ if(now == ed)return lim; int ans = 0; for(auto &id:paths[now]){ if(!edges[id].cap)continue; if(!lim)break; auto nxt = edges[id].to; if(level[nxt] != level[now]+1)continue; auto re = dfs(nxt,min(edges[id].cap,lim)); if(re == 0)continue; edges[id].cap -= re; edges[id^1].cap += re; ans += re; lim -= re; } return ans; } vector<pii> righ,down; int n,m; int calc(int x,int y){ edges.clear(); //cout<<x<<y<<endl; righ.clear(); down.clear(); queue<pii> q; q.push(make_pair(x,y)); done[x][y] = true; while(!q.empty()){ auto now = q.front(); q.pop(); assert(done[now.fs][now.sc]); if(now.sc<m-2&&s[now.fs].substr(now.sc,3)=="RGW"){ righ.push_back(now); pii nxt = make_pair(now.fs-1,now.sc+1); if(nxt.fs>=0&&nxt.sc<m&&now.fs<n-2&&!done[nxt.fs][nxt.sc]&&s[nxt.fs][nxt.sc] == 'R'&& s[nxt.fs+1][nxt.sc] == 'G'&&s[nxt.fs+2][nxt.sc] == 'W'){ done[nxt.fs][nxt.sc] = true; q.push(nxt); } nxt = make_pair(now.fs-2,now.sc+2); if(nxt.fs>=0&&nxt.sc<m&&now.fs<n-2&&!done[nxt.fs][nxt.sc]&&s[nxt.fs][nxt.sc] == 'R'&& s[nxt.fs+1][nxt.sc] == 'G'&&s[nxt.fs+2][nxt.sc] == 'W'){ done[nxt.fs][nxt.sc] = true; q.push(nxt); } } if(now.fs<n-2&&s[now.fs][now.sc] == 'R'&&s[now.fs+1][now.sc] == 'G'&&s[now.fs+2][now.sc] == 'W'){ down.push_back(now); pii nxt = make_pair(now.fs+1,now.sc-1); if(nxt.fs<n&&nxt.sc>=0&&nxt.sc<m-2&&s[nxt.fs].substr(nxt.sc,3)=="RGW"&&!done[nxt.fs][nxt.sc]){ done[nxt.fs][nxt.sc] = true; q.push(nxt); } nxt = make_pair(now.fs+2,now.sc-2); if(nxt.fs<n&&nxt.sc>=0&&nxt.sc<m-2&&s[nxt.fs].substr(nxt.sc,3)=="RGW"&&!done[nxt.fs][nxt.sc]){ done[nxt.fs][nxt.sc] = true; q.push(nxt); } } } paths = vector<vector<int>>(down.size()+righ.size()+2); assert(down.size()+righ.size()<mxn+mxn); level = vector<int>(paths.size()); sort(down.begin(),down.end()); sort(righ.begin(),righ.end()); for(int i = 0;i<down.size();i++){ pii tar = make_pair(down[i].fs,down[i].sc); auto pos = lower_bound(_all(righ),tar)-righ.begin(); if(pos != righ.size()&&righ[pos].fs == tar.fs&&righ[pos].sc == tar.sc)addedge(i+1,pos+down.size()+1); tar = make_pair(down[i].fs+1,down[i].sc-1); pos = lower_bound(_all(righ),tar)-righ.begin(); if(pos != righ.size()&&righ[pos].fs == tar.fs&&righ[pos].sc == tar.sc)addedge(i+1,pos+down.size()+1); tar = make_pair(down[i].fs+2,down[i].sc-2); pos = lower_bound(_all(righ),tar)-righ.begin(); if(pos != righ.size()&&righ[pos].fs == tar.fs&&righ[pos].sc == tar.sc)addedge(i+1,pos+down.size()+1); } for(int i = 1;i<=down.size();i++)addedge(0,i); for(int i = down.size()+1;i<paths.size()-1;i++)addedge(i,paths.size()-1); int ans = 0; //cout<<paths.size()<<endl<<endl; /* for(int i = 0;i<paths.size();i++){ for(auto &id:paths[i]){ cout<<i<<','<<edges[id].to<<' '; } } */ ed = paths.size()-1; st = 0; while(bfs()){ int re = 0; while(re = dfs(0,mxn*mxn))ans+= re; //cout<<re<<endl; } //cout<<"HI"<<endl; //for(auto &i:down)cout<<i.fs<<' '<<i.sc<<',';cout<<endl; //for(auto &i:righ)cout<<i.fs<<' '<<i.sc<<',';cout<<endl; //cout<<endl; return (int)down.size()+righ.size()-ans; } void solve(){ cin>>n>>m; int ans = 0; for(int i = 0;i<n;i++)cin>>s[i]; for(int i = 0;i<n;i++){ for(int j = 0;j<m;j++){ if(done[i][j])continue; //cout<<i<<' '<<j<<endl; if(j<m-2&&s[i].substr(j,3)=="RGW")ans += calc(i,j); else if(i<n-2&&s[i][j] == 'R'&&s[i+1][j] == 'G'&&s[i+2][j] == 'W')ans += calc(i,j); } } cout<<ans; return; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); solve(); }

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

dango_maker.cpp: In function 'int calc(int, int)':
dango_maker.cpp:124:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for(int i = 0;i<down.size();i++){
      |                ~^~~~~~~~~~~~
dango_maker.cpp:127:10: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   if(pos != righ.size()&&righ[pos].fs == tar.fs&&righ[pos].sc == tar.sc)addedge(i+1,pos+down.size()+1);
      |      ~~~~^~~~~~~~~~~~~~
dango_maker.cpp:130:10: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |   if(pos != righ.size()&&righ[pos].fs == tar.fs&&righ[pos].sc == tar.sc)addedge(i+1,pos+down.size()+1);
      |      ~~~~^~~~~~~~~~~~~~
dango_maker.cpp:133:10: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |   if(pos != righ.size()&&righ[pos].fs == tar.fs&&righ[pos].sc == tar.sc)addedge(i+1,pos+down.size()+1);
      |      ~~~~^~~~~~~~~~~~~~
dango_maker.cpp:135:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |  for(int i = 1;i<=down.size();i++)addedge(0,i);
      |                ~^~~~~~~~~~~~~
dango_maker.cpp:136:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |  for(int i = down.size()+1;i<paths.size()-1;i++)addedge(i,paths.size()-1);
      |                            ~^~~~~~~~~~~~~~~
dango_maker.cpp:151:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  151 |   while(re = dfs(0,mxn*mxn))ans+= re;
      |         ~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...