| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 153538 | 2019-09-14T15:09:53 Z | mhy908 | Dango Maker (JOI18_dango_maker) | C++14 | 2000 ms | 246860 KB |
#include <bits/stdc++.h>
#define pb push_back
#define INF 987654321
using namespace std;
typedef long long LL;
int n, m, x;
vector<char> str[3010];
int col[3010][3010][2], ans;
short re[3010][3010];
vector<int> link[6000001], id;
vector<int> par;
vector<bool> used;
vector<int> dist, A, B;
vector<vector<int> > vc;
map<int, int> mp;
queue<int> Q;
int findpar(int num)
{
if(num==par[num])return num;
return par[num]=findpar(par[num]);
}
void mergepar(int a, int b)
{
a=findpar(a);
b=findpar(b);
par[a]=par[b];
}
void bfs(int p)
{
for(int i=0; i<vc[p].size(); i++){
if(!used[i]){
dist[i]=0;
Q.push(i);
}
else dist[i]=INF;
}
while(!Q.empty()){
int a=Q.front();
Q.pop();
for(int b: link[vc[p][a]]){
b=mp[b];
if(B[b]!=-1&&dist[B[b]]==INF){
dist[B[b]]=dist[a]+1;
Q.push(B[b]);
}
}
}
}
bool dfs(int p, int a){
for(int b: link[vc[p][a]]){
b=mp[b];
if(B[b]==-1||dist[B[b]]==dist[a]+1&&dfs(p, B[b])){
used[a]=true;
A[a]=b;
B[b]=a;
return true;
}
}
return false;
}
int hopcroft_carp(int p)
{
int match=0;
while(1){
bfs(p);
int flow=0;
for(int i=0; i<vc[p].size(); i++)
if(!used[i]&&dfs(p, i))flow++;
if(!flow)break;
match+=flow;
}
return match/2;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++){
str[i].pb(0);
for(int j=1; j<=m; j++){
char y;
scanf(" %c", &y);
str[i].pb(y);
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(j+2<=m)
if(str[i][j]=='R'&&str[i][j+1]=='G'&&str[i][j+2]=='W'){
++x;
col[i][j][re[i][j]++]=x;
col[i][j+1][re[i][j+1]++]=x;
col[i][j+2][re[i][j+2]++]=x;
}
if(i+2<=n)
if(str[i][j]=='R'&&str[i+1][j]=='G'&&str[i+2][j]=='W'){
++x;
col[i][j][re[i][j]++]=x;
col[i+1][j][re[i+1][j]++]=x;
col[i+2][j][re[i+2][j]++]=x;
}
}
}
for(int i=1; i<=n; i++){
str[i].clear();
vector<char>().swap(str[i]);
}
for(int i=0; i<=x; i++)par.pb(i);
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(re[i][j]==2){
mergepar(col[i][j][1], col[i][j][0]);
link[col[i][j][1]].pb(col[i][j][0]);
link[col[i][j][0]].pb(col[i][j][1]);
}
}
}
for(int i=1; i<=x; i++){
id.pb(findpar(i));
}
sort(id.begin(), id.end());
id.erase(unique(id.begin(), id.end()), id.end());
int maxpar=1;
for(int i=1; i<=x; i++){
par[i]=lower_bound(id.begin(), id.end(), par[i])-id.begin();
maxpar=max(maxpar, par[i]+1);
}
id.clear();
vector<int>().swap(id);
vc.reserve(maxpar);
for(int i=1; i<=x; i++){
vc[par[i]].pb(i);
}
par.clear();
vector<int>().swap(par);
for(int i=0; i<maxpar; i++){
if(vc[i].size()==1)ans++;
else{
for(int j=0; j<vc[i].size(); j++)mp[vc[i][j]]=j;
used.reserve(vc[i].size()+2);
dist.reserve(vc[i].size()+2);
A.reserve(vc[i].size()+2);
B.reserve(vc[i].size()+2);
for(int j=0; j<A.size(); j++)A[j]=B[j]=-1;
ans+=vc[i].size()-hopcroft_carp(i);
mp.clear();
dist.clear();
A.clear();
B.clear();
used.clear();
vector<int>().swap(dist);
vector<int>().swap(A);
vector<int>().swap(B);
vector<bool>().swap(used);
}
}
printf("%d", ans);
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 139 ms | 141432 KB | Output is correct |
| 2 | Correct | 135 ms | 141304 KB | Output is correct |
| 3 | Execution timed out | 2056 ms | 246860 KB | Time limit exceeded |
| 4 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 139 ms | 141432 KB | Output is correct |
| 2 | Correct | 135 ms | 141304 KB | Output is correct |
| 3 | Execution timed out | 2056 ms | 246860 KB | Time limit exceeded |
| 4 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 139 ms | 141432 KB | Output is correct |
| 2 | Correct | 135 ms | 141304 KB | Output is correct |
| 3 | Execution timed out | 2056 ms | 246860 KB | Time limit exceeded |
| 4 | Halted | 0 ms | 0 KB | - |