Submission #136336

#	Time	Username	Problem	Language	Result	Execution time	Memory
136336		KLPP	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	28 ms	23956 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[10000000];
int size;
int independent;
vector<int> graph[1000000];
void DFS(int node, int parity){
  independent+=parity;
  visited[node]=true;
  size++;
  trav(v,graph[node]){
    if(!visited[v])DFS(v,(parity+1)%2);
  }
}
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){
    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]){
      size=0;
      independent=0;
      DFS(i,0);
      ans+=max(independent,size-independent);
    }
  }
  cout<<ans<<endl;
  return 0;
}

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