Submission #136368

#	Time	Username	Problem	Language	Result	Execution time	Memory
136368		KLPP	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	1200 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[1000000];
int size;
int independent;
vector<int> graph[1000000];
queue<int> q;
vector<int> tree[1000000];
int DP[1000000][2];
void DFS(int node){
  visited[node]=true;
  //q.push(node);
  trav(v,graph[node]){
    if(!visited[v]){
      tree[node].push_back(v);
      DFS(v);
    }
  }
}
int compute(int node, int x){
  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){
    DP[i][0]=-1;
    DP[i][1]=-1;
    /*trav(v,graph[i]){
      cout<<v<<" ";
    }
    cout<<endl;*/
  }
  rep(i,0,V+H){
    visited[i]=false;
  }
  int ans=0;
  rep(i,0,V+H){
    if(!visited[i]){
      
      DFS(i);
      /*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;*/
      ans+=max(compute(i,0),compute(i,1));
      
      //cout<<independent<<" "<<size-independent<<"A"<<endl;
    }
  }
  /*rep(i,0,V+H){
    cout<<compute(i,0)<<" "<<compute(i,1)<<endl;
  }*/
  cout<<ans<<endl;
  
  return 0;
}

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