Submission #359196
Source Code Expand
//ドワンゴ フィッシング 8020 //SYAKYO http://dwango2015-honsen.contest.atcoder.jp/submissions/337993 #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(match)); for(int v=0;v<V;v++){ if(match[v] < 0){ memset(used,0,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; //足りない分ずらす 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 | 90 |
Code Size | 1650 Byte |
Status | AC |
Exec Time | 295 ms |
Memory | 2032 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 60 / 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 | 1816 KB |
sample_02.txt | AC | 27 ms | 1772 KB |
subtask1_01.txt | AC | 28 ms | 1772 KB |
subtask1_02.txt | AC | 29 ms | 1776 KB |
subtask1_03.txt | AC | 29 ms | 1772 KB |
subtask1_04.txt | AC | 29 ms | 1816 KB |
subtask1_05.txt | AC | 29 ms | 1768 KB |
subtask1_06.txt | AC | 39 ms | 1820 KB |
subtask1_07.txt | AC | 29 ms | 1892 KB |
subtask1_08.txt | AC | 29 ms | 1800 KB |
subtask1_09.txt | AC | 28 ms | 1772 KB |
subtask1_10.txt | AC | 30 ms | 1816 KB |
subtask1_11.txt | AC | 28 ms | 1816 KB |
subtask1_12.txt | AC | 29 ms | 1768 KB |
subtask1_13.txt | AC | 29 ms | 1768 KB |
subtask1_14.txt | AC | 31 ms | 1772 KB |
subtask1_15.txt | AC | 29 ms | 1820 KB |
subtask1_16.txt | AC | 28 ms | 1816 KB |
subtask2_01.txt | AC | 55 ms | 1896 KB |
subtask2_02.txt | AC | 176 ms | 1896 KB |
subtask2_03.txt | AC | 38 ms | 1892 KB |
subtask2_04.txt | AC | 49 ms | 1896 KB |
subtask2_05.txt | AC | 34 ms | 1896 KB |
subtask2_06.txt | AC | 34 ms | 2024 KB |
subtask2_07.txt | AC | 34 ms | 2024 KB |
subtask2_08.txt | AC | 58 ms | 1940 KB |
subtask2_09.txt | AC | 178 ms | 1900 KB |
subtask2_10.txt | AC | 40 ms | 1896 KB |
subtask2_11.txt | AC | 160 ms | 1896 KB |
subtask2_12.txt | AC | 71 ms | 1896 KB |
subtask2_13.txt | AC | 45 ms | 1892 KB |
subtask2_14.txt | AC | 178 ms | 1900 KB |
subtask2_15.txt | AC | 55 ms | 1900 KB |
subtask2_16.txt | AC | 110 ms | 1852 KB |
subtask2_17.txt | AC | 84 ms | 1948 KB |
subtask2_18.txt | AC | 134 ms | 1892 KB |
subtask2_19.txt | AC | 95 ms | 2032 KB |
subtask2_20.txt | AC | 295 ms | 1892 KB |
subtask2_21.txt | AC | 96 ms | 1896 KB |
subtask2_22.txt | AC | 100 ms | 1900 KB |
subtask2_23.txt | AC | 165 ms | 1892 KB |
subtask2_24.txt | AC | 67 ms | 1884 KB |
subtask2_25.txt | AC | 99 ms | 1892 KB |
subtask2_26.txt | AC | 55 ms | 1900 KB |
subtask2_27.txt | AC | 178 ms | 1900 KB |
subtask2_28.txt | AC | 197 ms | 1900 KB |