Submission #211271


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rrep(i,n) for(int i=(int)(n)-1; i>=0; i--)
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define iter(c) __typeof((c).begin())
#define tr(it,c) for(iter(c) it=(c).begin(); it!=(c).end(); it++)
#define pb(a) push_back(a)
#define pr(a) cout << (a) << endl
#define PR(a,b) cout << (a) << " " << (b) << endl
#define F first
#define S second
typedef long long ll;
typedef pair<int,int> P;
const int MAX=1000000001;
const ll MAXL=1000000000000000001LL;
const ll mod=1000000007;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

const int MAX_V=50;
 
struct edge{
  int to,cap,rev;
};
vector<edge> G[MAX_V];
bool used[MAX_V];
 
void add_edge(int from,int to, int cap) {
  G[from].push_back((edge){to,cap,G[to].size()});
  G[to].push_back((edge){from,0,G[from].size()-1});
}
 
int dfs(int v,int t,int f) {
  if(v==t) return f;
  used[v]=true;
  rep(i,G[v].size()) {
    edge &e=G[v][i];
    if(!used[e.to] && e.cap>0) {
      int d=dfs(e.to,t,min(f,e.cap));
      if(d>0) {
	e.cap-=d;
	G[e.to][e.rev].cap+=d;
	return d;
      }
    }
  }
  return 0;
}
 
int max_flow(int s,int t) {
  int flow=0;
  for(;;) {
    memset(used,0,sizeof(used));
    int f=dfs(s,t,MAX);
    if(f==0) return flow;
    flow+=f;
  }
}

int main() {
  int n,m;
  cin >> n >> m;
  vector<string> a(n);
  rep(i,n) {
    cin >> a[i];
    add_edge(i,20,1);
  }
  rep(i,n-1) {
    REP(j,i+1,n) {
      bool ck=true;
      rep(k,m) {
	if(a[i][k]!='*' && a[j][k]!='*') {
	  if(a[i][k]!=a[j][k]) ck=false;
	}
      }
      if(ck) {
	add_edge(i,j,1);
      }
    }
  }
  int ans=MAX;
  int cnt=0;
  rep(i,n) {
    if(max_flow(i,20)>0) cnt++;
  }
  ans=min(ans,cnt);
  rep(i,MAX_V)G[i].clear();
  rep(i,n) {
    add_edge(i,20,1);
  }
  rep(i,n-1) {
    REP(j,i+1,n) {
      bool ck=true;
      rep(k,m) {
	if(a[i][k]!='*' && a[j][k]!='*') {
	  if(a[i][k]!=a[j][k]) ck=false;
	}
      }
      if(ck) {
	add_edge(j,i,1);
      }
    }
  }
  cnt=0;
  rep(i,n) {
    if(max_flow(i,20)>0) cnt++;
  }
  ans=min(ans,cnt);
  rep(i,MAX_V)G[i].clear();
  rep(i,n) {
    add_edge(i,20,1);
  }
  rep(i,n-1) {
    REP(j,i+1,n) {
      bool ck=true;
      rep(k,m) {
	if(a[i][k]!='*' && a[j][k]!='*') {
	  if(a[i][k]!=a[j][k]) ck=false;
	}
      }
      if(ck) {
	add_edge(i,j,1);
	add_edge(j,i,1);
      }
    }
  }
  cnt=0;
  rep(i,n) {
    if(max_flow(i,20)>0) cnt++;
  }
  ans=min(ans,cnt);
  pr(ans);
  return 0;
}

Submission Info

Submission Time
Task C - 天下一文字列集合
User s1200008
Language C++ (G++ 4.6.4)
Score 20
Code Size 2635 Byte
Status
Exec Time 504 ms
Memory 2396 KB

Test Cases

Set Name Score / Max Score Test Cases
small 20 / 20 00_small100.txt, 00_small101.txt, 00_small102.txt, 00_small103.txt, 00_small104.txt, 00_small105.txt, 00_small106.txt, 00_small107.txt, 00_small108.txt, 00_small109.txt, 00_small110.txt, 00_small111.txt, 00_small112.txt, 00_small113.txt, 00_small114.txt, 00_small115.txt, 00_small116.txt, 00_small117.txt
medium 0 / 30 00_small100.txt, 00_small101.txt, 00_small102.txt, 00_small103.txt, 00_small104.txt, 00_small105.txt, 00_small106.txt, 00_small107.txt, 00_small108.txt, 00_small109.txt, 00_small110.txt, 00_small111.txt, 00_small112.txt, 00_small113.txt, 00_small114.txt, 00_small115.txt, 00_small116.txt, 00_small117.txt, 01_medium100.txt, 01_medium101.txt, 01_medium102.txt, 01_medium103.txt, 01_medium104.txt, 01_medium105.txt, 01_medium106.txt, 01_medium107.txt, 01_medium108.txt, 01_medium109.txt, 01_medium110.txt, 01_medium111.txt, 01_medium112.txt, 01_medium113.txt, 01_medium114.txt, 01_medium115.txt, 01_medium116.txt, 01_medium117.txt, 01_medium118.txt, 01_medium119.txt, 01_medium120.txt, 01_medium121.txt, 01_medium122.txt, 01_medium123.txt, 01_medium124.txt, 01_medium125.txt, 01_medium126.txt, 01_sample0.txt
All 0 / 50 00_small100.txt, 00_small101.txt, 00_small102.txt, 00_small103.txt, 00_small104.txt, 00_small105.txt, 00_small106.txt, 00_small107.txt, 00_small108.txt, 00_small109.txt, 00_small110.txt, 00_small111.txt, 00_small112.txt, 00_small113.txt, 00_small114.txt, 00_small115.txt, 00_small116.txt, 00_small117.txt, 01_medium100.txt, 01_medium101.txt, 01_medium102.txt, 01_medium103.txt, 01_medium104.txt, 01_medium105.txt, 01_medium106.txt, 01_medium107.txt, 01_medium108.txt, 01_medium109.txt, 01_medium110.txt, 01_medium111.txt, 01_medium112.txt, 01_medium113.txt, 01_medium114.txt, 01_medium115.txt, 01_medium116.txt, 01_medium117.txt, 01_medium118.txt, 01_medium119.txt, 01_medium120.txt, 01_medium121.txt, 01_medium122.txt, 01_medium123.txt, 01_medium124.txt, 01_medium125.txt, 01_medium126.txt, 01_sample0.txt, 02_large100.txt, 02_large101.txt, 02_large102.txt, 02_large103.txt, 02_large104.txt, 02_large105.txt, 02_large106.txt, 02_large107.txt, 02_large108.txt, 02_large109.txt, 02_large110.txt, 02_large111.txt, 02_large112.txt, 02_large113.txt, 02_large114.txt, 02_large115.txt, 02_large116.txt, 02_large117.txt, 02_large118.txt, 02_large119.txt, 02_large120.txt, 02_large121.txt, 02_large122.txt, 02_large123.txt, 02_large124.txt, 02_large125.txt, 02_large126.txt, 02_large127.txt, 02_large128.txt, 02_large129.txt, 02_large130.txt
Case Name Status Exec Time Memory
00_small100.txt 22 ms 920 KB
00_small101.txt 21 ms 796 KB
00_small102.txt 19 ms 800 KB
00_small103.txt 19 ms 800 KB
00_small104.txt 22 ms 800 KB
00_small105.txt 21 ms 924 KB
00_small106.txt 20 ms 916 KB
00_small107.txt 20 ms 800 KB
00_small108.txt 21 ms 804 KB
00_small109.txt 20 ms 800 KB
00_small110.txt 19 ms 800 KB
00_small111.txt 20 ms 924 KB
00_small112.txt 21 ms 764 KB
00_small113.txt 21 ms 824 KB
00_small114.txt 19 ms 800 KB
00_small115.txt 20 ms 796 KB
00_small116.txt 20 ms 800 KB
00_small117.txt 20 ms 928 KB
01_medium100.txt 20 ms 800 KB
01_medium101.txt 20 ms 788 KB
01_medium102.txt 20 ms 804 KB
01_medium103.txt 22 ms 932 KB
01_medium104.txt 21 ms 800 KB
01_medium105.txt 20 ms 800 KB
01_medium106.txt 20 ms 796 KB
01_medium107.txt 20 ms 748 KB
01_medium108.txt 20 ms 800 KB
01_medium109.txt 20 ms 796 KB
01_medium110.txt 20 ms 800 KB
01_medium111.txt 21 ms 928 KB
01_medium112.txt 21 ms 812 KB
01_medium113.txt 19 ms 916 KB
01_medium114.txt 19 ms 800 KB
01_medium115.txt 20 ms 800 KB
01_medium116.txt 20 ms 840 KB
01_medium117.txt 21 ms 928 KB
01_medium118.txt 21 ms 800 KB
01_medium119.txt 22 ms 804 KB
01_medium120.txt 22 ms 924 KB
01_medium121.txt 23 ms 808 KB
01_medium122.txt 22 ms 808 KB
01_medium123.txt 22 ms 804 KB
01_medium124.txt 20 ms 804 KB
01_medium125.txt 21 ms 920 KB
01_medium126.txt 21 ms 800 KB
01_sample0.txt 20 ms 800 KB
02_large100.txt 154 ms 2336 KB
02_large101.txt 156 ms 2344 KB
02_large102.txt 158 ms 2336 KB
02_large103.txt 157 ms 2340 KB
02_large104.txt 157 ms 2268 KB
02_large105.txt 158 ms 2344 KB
02_large106.txt 49 ms 1132 KB
02_large107.txt 26 ms 924 KB
02_large108.txt 22 ms 748 KB
02_large109.txt 21 ms 800 KB
02_large110.txt 22 ms 804 KB
02_large111.txt 373 ms 2344 KB
02_large112.txt 259 ms 2340 KB
02_large113.txt 37 ms 1056 KB
02_large114.txt 335 ms 2284 KB
02_large115.txt 158 ms 2344 KB
02_large116.txt 335 ms 2332 KB
02_large117.txt 26 ms 1012 KB
02_large118.txt 402 ms 2344 KB
02_large119.txt 464 ms 2344 KB
02_large120.txt 494 ms 2336 KB
02_large121.txt 504 ms 2396 KB
02_large122.txt 483 ms 2340 KB
02_large123.txt 435 ms 2340 KB
02_large124.txt 366 ms 2348 KB
02_large125.txt 293 ms 2340 KB
02_large126.txt 224 ms 2336 KB
02_large127.txt 371 ms 2336 KB
02_large128.txt 201 ms 2344 KB
02_large129.txt 470 ms 2340 KB
02_large130.txt 189 ms 2336 KB