Submission #136407

#	Time	Username	Problem	Language	Result	Execution time	Memory
136407		KLPP	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	1089 ms	262144 KiB

dango_maker

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
int has[3000][3000][2];
int n,m;
bool valid(int x, int y){
  if(x>=0 && x<n && y>=0 && y<m)return true;
  return false;
}
bool visited[3000000];
int size;
bool visited2[3000];
int independent;
vector<int> graph[3000000];
vector<int> tree[3000];
short int DP[3000][2];
vector<int> cmp;
vector<int> graph2[3000];
void DFS(int node){
  visited[node]=true;
  cmp.push_back(node);
  trav(v,graph[node]){
    if(!visited[v]){
      //tree[node].push_back(v);
      DFS(v);
    }
  }
}
void DFS2(int node){
  visited2[node]=true;
  trav(v,graph2[node]){
    if(!visited2[v]){
      tree[node].push_back(v);
      DFS2(v);
    }
  }
}
int BS(int lo, int hi, int target){
  int mid=(hi+lo)/2;
  if(cmp[mid]==target)return mid;
  if(cmp[mid]<target)return BS(mid+1,hi,target);
  if(cmp[mid]>target)return BS(lo,mid-1,target);
}
int compute(int node, int x){
  //cout<<node<<"C"<<x<<endl;
  if(DP[node][x]!=-1)return DP[node][x];
  DP[node][x]=0;
  if(x==0){
    trav(v,tree[node]){
      DP[node][x]+=max(compute(v,0),compute(v,1));
    }
    return DP[node][x];
  }
  DP[node][x]++;
  trav(v,tree[node]){
    DP[node][x]+=compute(v,0);
  }
  return DP[node][x];
}
int main(){
  
  cin>>n>>m;
  string table[n];
  rep(i,0,n){
    cin>>table[i];
  }
  int V=0;
  int H=0;
  vector<pii> v;
  vector<pii> h;
  rep(i,0,n){
    rep(j,0,m){
      has[i][j][0]=-1;
      has[i][j][1]=-1;
      if(table[i][j]=='R'){
	if(i+2<n && table[i+1][j]=='G' && table[i+2][j]=='W'){
	  has[i][j][0]=V;
	  V++;
	  v.push_back(pii(i,j));
	}
	if(j+2<m && table[i][j+1]=='G' && table[i][j+2]=='W'){
	  has[i][j][1]=H;
	  H++;
	  h.push_back(pii(i,j));
	}
      }
    }
  }
  rep(i,0,n){
    rep(j,0,m){
      if(has[i][j][0]!=-1){
	if(has[i][j][1]!=-1){
	  graph[has[i][j][0]].push_back(has[i][j][1]+V);
	  graph[has[i][j][1]+V].push_back(has[i][j][0]);
	}
	if(valid(i+1,j-1) && has[i+1][j-1][1]!=-1){
	  graph[has[i][j][0]].push_back(has[i+1][j-1][1]+V);
	  graph[has[i+1][j-1][1]+V].push_back(has[i][j][0]);
	}
	if(valid(i+2,j-2) && has[i+2][j-2][1]!=-1){
	  graph[has[i][j][0]].push_back(has[i+2][j-2][1]+V);
	  graph[has[i+2][j-2][1]+V].push_back(has[i][j][0]);
	}
      }
    }
  }
  //cout<<V+H<<endl;
  
  rep(i,0,V+H){
    visited[i]=false;
  }
  int ans=0;
  rep(i,0,V+H){
    if(!visited[i]){
      
      DFS(i);
      sort(cmp.begin(),cmp.end());
      rep(i,0,cmp.size()){
	visited2[i]=false;
      }
      rep(i,0,cmp.size()){
	DP[i][0]=-1;
	DP[i][1]=-1;
    
      }
      //cout<<cmp.size()<<endl;
      /*trav(x,cmp)cout<<x<<endl;
      cout<<endl;*/
      trav(x,cmp){
	trav(y,graph[x]){
	  //cout<<BS(0,cmp.size()-1,x)<<"A "<<BS(0,cmp.size()-1,y)<<endl;
	  graph2[BS(0,cmp.size()-1,x)].push_back(BS(0,cmp.size()-1,y));
	  
	}
      }
      DFS2(0);
      /*while(!q.empty()){
	//if(q.front()<V)cout<<v[q.front()].first<<","<<v[q.front()].second<<" ";
	//if(q.front()>=V)cout<<h[q.front()-V].first<<","<<h[q.front()-V].second<<" ";
	visited[q.front()]=false;
	q.pop();
      }//cout<<endl;*/
      //cout<<compute(0,0)<<" "<<compute(0,1)<<endl;
      ans+=max(compute(0,0),compute(0,1));
      rep(i,0,cmp.size()){
	graph2[i].clear();
	tree[i].clear();
      }
      cmp.clear();
      //cout<<independent<<" "<<size-independent<<"A"<<endl;
    }
  }
  /*rep(i,0,V+H){
    cout<<compute(i,0)<<" "<<compute(i,1)<<endl;
  }*/
  cout<<ans<<endl;
  
  return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
dango_maker.cpp:122:11:
       rep(i,0,cmp.size()){
           ~~~~~~~~~~~~~~         
dango_maker.cpp:122:7: note: in expansion of macro 'rep'
       rep(i,0,cmp.size()){
       ^~~
dango_maker.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
dango_maker.cpp:125:11:
       rep(i,0,cmp.size()){
           ~~~~~~~~~~~~~~         
dango_maker.cpp:125:7: note: in expansion of macro 'rep'
       rep(i,0,cmp.size()){
       ^~~
dango_maker.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
dango_maker.cpp:149:11:
       rep(i,0,cmp.size()){
           ~~~~~~~~~~~~~~         
dango_maker.cpp:149:7: note: in expansion of macro 'rep'
       rep(i,0,cmp.size()){
       ^~~
dango_maker.cpp: In function 'int BS(int, int, int)':
dango_maker.cpp:47:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 0 / 67