Submission #359193
Source Code Expand
//ドワンゴ フィッシング 8020 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; typedef pair<int,pair<int,int>> PP; typedef long long ll; const double EPS = 1e-9; const int INF = 1e9; const int MOD = 1e9+7; int dy[] = {0,1,0,-1}; int dx[] = {1,0,-1,0}; const int MAX_V = 400; vector<int> G[MAX_V]; int match[MAX_V]; bool used[MAX_V]; int V; void add_edge(int u,int v){ G[u].push_back(v); G[v].push_back(u); } bool dfs(int v){ used[v] = true; for(int i=0;i<G[v].size();i++){ int u = G[v][i],w = match[u]; if(w < 0 || (!used[w] && dfs(w))){ match[v] = u; match[u] = v; return true; } } return false; } int nibu(){ int res = 0; memset(match,-1,sizeof(used)); for(int v=0;v<V;v++){ if(match[v] < 0){ memset(used,-1,sizeof(used)); if(dfs(v))res++; } } return res; } int N; string s[200]; vector<int> nums; bool solve(){ int N; cin >> N; V = 2*N; for(int i=0;i<N;i++){ cin >> s[i]; } for(int i=0;i<N;i++)nums.push_back(s[i].size()); sort(begin(nums),end(nums)); int mn = 1e9; for(int i=0;i<N;i++)mn = min(mn,nums[i]-i); for(int c=0;c<26;c++){ for(int i=0;i<mn;){ for(int j=0;j<V;j++)G[j].clear(); for(int j=0;j<N;j++)for(int k=0;k<N;k++){ if(s[j].size() > k+i && s[j][k+i] == 'a' + c)add_edge(j,k+N); } int a = nibu(); if(a == N)return true; //1個ずらしても、最大1しかマッチングは増えない //足りない分ずらす i += N - a; } } return false; } int main(void) { if(solve()) puts("YES"); else puts("NO"); return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - コメント |
User | tkzw_21 |
Language | C++11 (GCC 4.8.1) |
Score | 0 |
Code Size | 1649 Byte |
Status | WA |
Exec Time | 72 ms |
Memory | 1332 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 30 | 0 / 60 | ||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt |
Subtask1 | sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt |
Subtask2 | subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 29 ms | 1072 KB |
sample_02.txt | AC | 30 ms | 1076 KB |
subtask1_01.txt | AC | 28 ms | 1196 KB |
subtask1_02.txt | AC | 29 ms | 1172 KB |
subtask1_03.txt | AC | 30 ms | 1104 KB |
subtask1_04.txt | AC | 31 ms | 1076 KB |
subtask1_05.txt | AC | 29 ms | 1072 KB |
subtask1_06.txt | AC | 31 ms | 1072 KB |
subtask1_07.txt | WA | 32 ms | 1176 KB |
subtask1_08.txt | AC | 30 ms | 1176 KB |
subtask1_09.txt | WA | 30 ms | 1104 KB |
subtask1_10.txt | AC | 29 ms | 1108 KB |
subtask1_11.txt | AC | 29 ms | 1076 KB |
subtask1_12.txt | WA | 29 ms | 1184 KB |
subtask1_13.txt | WA | 28 ms | 1072 KB |
subtask1_14.txt | WA | 31 ms | 1184 KB |
subtask1_15.txt | WA | 31 ms | 1188 KB |
subtask1_16.txt | AC | 30 ms | 1204 KB |
subtask2_01.txt | WA | 43 ms | 1204 KB |
subtask2_02.txt | AC | 43 ms | 1196 KB |
subtask2_03.txt | WA | 43 ms | 1200 KB |
subtask2_04.txt | AC | 45 ms | 1324 KB |
subtask2_05.txt | WA | 43 ms | 1200 KB |
subtask2_06.txt | AC | 36 ms | 1316 KB |
subtask2_07.txt | WA | 34 ms | 1320 KB |
subtask2_08.txt | WA | 45 ms | 1200 KB |
subtask2_09.txt | AC | 46 ms | 1196 KB |
subtask2_10.txt | WA | 39 ms | 1248 KB |
subtask2_11.txt | WA | 44 ms | 1324 KB |
subtask2_12.txt | WA | 45 ms | 1232 KB |
subtask2_13.txt | WA | 45 ms | 1196 KB |
subtask2_14.txt | AC | 43 ms | 1228 KB |
subtask2_15.txt | WA | 46 ms | 1204 KB |
subtask2_16.txt | AC | 62 ms | 1196 KB |
subtask2_17.txt | AC | 72 ms | 1256 KB |
subtask2_18.txt | AC | 63 ms | 1200 KB |
subtask2_19.txt | AC | 69 ms | 1332 KB |
subtask2_20.txt | AC | 42 ms | 1200 KB |
subtask2_21.txt | AC | 43 ms | 1200 KB |
subtask2_22.txt | WA | 44 ms | 1236 KB |
subtask2_23.txt | WA | 42 ms | 1200 KB |
subtask2_24.txt | AC | 43 ms | 1200 KB |
subtask2_25.txt | WA | 44 ms | 1320 KB |
subtask2_26.txt | WA | 42 ms | 1332 KB |
subtask2_27.txt | AC | 41 ms | 1200 KB |
subtask2_28.txt | AC | 40 ms | 1204 KB |