Submission #00052

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<vector>
using namespace std;
vector<int>g[1000];
int n,v,ans,match[1000],used[1000];
string m[500];
bool dfs(int u){
used[u]=1;
for(int i=0;i<g[u].size();i++){
int w=g[u][i];
int mm=match[w];
if(mm<0||!used[mm]&&dfs(mm)){
match[u]=w;
match[w]=u;
return true;
}
}
return false;
}
main(){
cin>>n;v=n*2;
for(int i=0;i<n;i++){
cin>>m[i];
for(int j=0;j<n;j++){
if(m[i][j]=='#'){
g[i].push_back(j+n);
g[j+n].push_back(i);
}
}
}
for(int i=0;i<v;i++)match[i]=-1;
for(int u=0;u<v;u++){
if(match[u]<0){
for(int i=0;i<v;i++)used[i]=0;
if(dfs(u))ans++;
}
}
cout<<ans<<endl;
}

ステータス

項目 データ
問題 0006 - 回れ雛月花 -Hard
ユーザー名 kotatsugame
投稿日時 2017-10-25 17:50:24
言語 C++11
状態 Accepted
得点 6
ソースコード長 629 Byte
最大実行時間 37 ms
最大メモリ使用量 1512 KB

セット

セット 得点 Cases
1 Easy 0.3 / 0.3 *easy
2 Normal 0.6 / 0.6 *normal
3 Hard 0.9 / 0.9 *hard
4 Extra 1.2 / 1.2 *extra
5 All 3 / 3 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
Input01_easy AC 14 ms 480 KB
1
5
Input02_easy AC 22 ms 664 KB
1
5
Input03_easy AC 18 ms 716 KB
1
5
Input04_easy AC 14 ms 512 KB
1
5
Input05_easy AC 18 ms 572 KB
1
5
Input06_normal AC 17 ms 628 KB
2
5
Input07_normal AC 18 ms 424 KB
2
5
Input08_normal AC 19 ms 468 KB
2
5
Input09_normal AC 22 ms 508 KB
2
5
Input10_normal AC 21 ms 552 KB
2
5
Input11_hard AC 19 ms 600 KB
3
5
Input12_hard AC 23 ms 616 KB
3
5
Input13_hard AC 27 ms 1004 KB
3
5
Input14_hard AC 17 ms 864 KB
3
5
Input15_hard AC 28 ms 1088 KB
3
5
Input16_extra AC 26 ms 1440 KB
4
5
Input17_extra AC 27 ms 1512 KB
4
5
Input18_extra AC 24 ms 1320 KB
4
5
Input19_extra AC 37 ms 1264 KB
4
5
Input20_extra AC 30 ms 1208 KB
4
5
Input21_extra AC 29 ms 1280 KB
4
5
Input22_extra AC 30 ms 1352 KB
4
5
Input23_extra AC 32 ms 1292 KB
4
5
Input24_extra AC 23 ms 1364 KB
4
5
Input25_extra AC 37 ms 1428 KB
4
5
Input26_extra AC 29 ms 1120 KB
4
5
Input27_extra AC 25 ms 1272 KB
4
5
Input28_extra AC 27 ms 1296 KB
4
5
Input29_extra AC 26 ms 1196 KB
4
5
Input30_extra AC 22 ms 1216 KB
4
5