Submission #758230
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define mp make_pair #define pb push_back #define fi first #define se second inline int dist(string x, string y) { int ret=0; rep(i,x.size()) if(x[i]!=y[i]) ++ret; return ret; } int main() { string f,l; int n; cin >>f >>l; cin >>n; vector<string> s; s.pb(f); rep(i,n) { string t; cin >>t; s.pb(t); } s.pb(l); n+=2; /* 0 : first 1~n-2 : words n-1 : last */ if(f==l) { printf("0\n"); cout << f << endl; cout << l << endl; return 0; } vector<int> G[1002]; rep(i,n) { rep(j,i) { if(dist(s[i],s[j])==1) { G[i].pb(j); G[j].pb(i); } } } int par[1002]; int d[1002]; const int INF=1000000; fill(d,d+n,INF); fill(par,par+n,-1); d[0]=0; queue<int> que; que.push(0); while(!que.empty()) { int v=que.front(); que.pop(); rep(i,G[v].size()) { int nx=G[v][i]; if(d[nx]>d[v]+1) { d[nx]=d[v]+1; par[nx]=v; que.push(nx); } } } if(d[n-1]==INF) printf("-1\n"); else { printf("%d\n", d[n-1]-1); vector<string> ans; int now=n-1; while(par[now]!=0) { ans.pb(s[par[now]]); now=par[now]; } reverse(all(ans)); cout << f << endl; for(const auto &x:ans) cout << x << endl; cout << l << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - ダブレット |
User | imulan |
Language | C++11 (GCC 4.8.1) |
Score | 100 |
Code Size | 1998 Byte |
Status | AC |
Exec Time | 192 ms |
Memory | 5032 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_rand_00.txt, 01_rand_01.txt, 01_rand_02.txt, 01_rand_03.txt, 01_rand_04.txt, 01_rand_05.txt, 01_rand_06.txt, 01_rand_07.txt, 01_rand_08.txt, 01_rand_09.txt, 01_rand_10.txt, 01_rand_11.txt, 01_rand_12.txt, 01_rand_13.txt, 01_rand_14.txt, 01_rand_15.txt, 01_rand_16.txt, 01_rand_17.txt, 01_rand_18.txt, 01_rand_19.txt, 02_maxrand_00.txt, 02_maxrand_01.txt, 02_maxrand_02.txt, 02_maxrand_03.txt, 02_maxrand_04.txt, 02_maxrand_05.txt, 02_maxrand_06.txt, 02_maxrand_07.txt, 02_maxrand_08.txt, 02_maxrand_09.txt, 02_maxrand_10.txt, 02_maxrand_11.txt, 02_maxrand_12.txt, 02_maxrand_13.txt, 02_maxrand_14.txt, 02_maxrand_15.txt, 02_maxrand_16.txt, 02_maxrand_17.txt, 02_maxrand_18.txt, 02_maxrand_19.txt, 03_long_00.txt, 03_long_01.txt, 03_long_02.txt, 03_long_03.txt, 03_long_04.txt, 03_long_05.txt, 03_long_06.txt, 03_long_07.txt, 03_long_08.txt, 03_long_09.txt, 03_long_10.txt, 03_long_11.txt, 03_long_12.txt, 03_long_13.txt, 03_long_14.txt, 03_long_15.txt, 03_long_16.txt, 03_long_17.txt, 03_long_18.txt, 03_long_19.txt, 04_manygroup_00.txt, 04_manygroup_01.txt, 04_manygroup_02.txt, 04_manygroup_03.txt, 04_manygroup_04.txt, 04_manygroup_05.txt, 04_manygroup_06.txt, 04_manygroup_07.txt, 04_manygroup_08.txt, 04_manygroup_09.txt, 04_manygroup_10.txt, 04_manygroup_11.txt, 04_manygroup_12.txt, 04_manygroup_13.txt, 04_manygroup_14.txt, 04_manygroup_15.txt, 04_manygroup_16.txt, 04_manygroup_17.txt, 04_manygroup_18.txt, 04_manygroup_19.txt, 10_min_01.txt, 10_min_02.txt, 10_min_03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01.txt | AC | 28 ms | 800 KB |
00_sample_02.txt | AC | 23 ms | 800 KB |
00_sample_03.txt | AC | 25 ms | 928 KB |
01_rand_00.txt | AC | 165 ms | 928 KB |
01_rand_01.txt | AC | 26 ms | 920 KB |
01_rand_02.txt | AC | 135 ms | 924 KB |
01_rand_03.txt | AC | 32 ms | 1056 KB |
01_rand_04.txt | AC | 76 ms | 868 KB |
01_rand_05.txt | AC | 24 ms | 924 KB |
01_rand_06.txt | AC | 71 ms | 800 KB |
01_rand_07.txt | AC | 51 ms | 924 KB |
01_rand_08.txt | AC | 30 ms | 928 KB |
01_rand_09.txt | AC | 49 ms | 928 KB |
01_rand_10.txt | AC | 116 ms | 932 KB |
01_rand_11.txt | AC | 175 ms | 932 KB |
01_rand_12.txt | AC | 87 ms | 928 KB |
01_rand_13.txt | AC | 153 ms | 940 KB |
01_rand_14.txt | AC | 131 ms | 4776 KB |
01_rand_15.txt | AC | 50 ms | 924 KB |
01_rand_16.txt | AC | 115 ms | 4508 KB |
01_rand_17.txt | AC | 75 ms | 796 KB |
01_rand_18.txt | AC | 27 ms | 932 KB |
01_rand_19.txt | AC | 112 ms | 920 KB |
02_maxrand_00.txt | AC | 172 ms | 932 KB |
02_maxrand_01.txt | AC | 173 ms | 932 KB |
02_maxrand_02.txt | AC | 142 ms | 5032 KB |
02_maxrand_03.txt | AC | 177 ms | 932 KB |
02_maxrand_04.txt | AC | 132 ms | 864 KB |
02_maxrand_05.txt | AC | 176 ms | 932 KB |
02_maxrand_06.txt | AC | 176 ms | 932 KB |
02_maxrand_07.txt | AC | 180 ms | 936 KB |
02_maxrand_08.txt | AC | 182 ms | 932 KB |
02_maxrand_09.txt | AC | 164 ms | 936 KB |
02_maxrand_10.txt | AC | 175 ms | 928 KB |
02_maxrand_11.txt | AC | 166 ms | 928 KB |
02_maxrand_12.txt | AC | 175 ms | 940 KB |
02_maxrand_13.txt | AC | 168 ms | 936 KB |
02_maxrand_14.txt | AC | 179 ms | 932 KB |
02_maxrand_15.txt | AC | 168 ms | 928 KB |
02_maxrand_16.txt | AC | 192 ms | 928 KB |
02_maxrand_17.txt | AC | 132 ms | 1316 KB |
02_maxrand_18.txt | AC | 163 ms | 820 KB |
02_maxrand_19.txt | AC | 135 ms | 920 KB |
03_long_00.txt | AC | 178 ms | 936 KB |
03_long_01.txt | AC | 166 ms | 940 KB |
03_long_02.txt | AC | 135 ms | 928 KB |
03_long_03.txt | AC | 134 ms | 932 KB |
03_long_04.txt | AC | 152 ms | 932 KB |
03_long_05.txt | AC | 143 ms | 924 KB |
03_long_06.txt | AC | 130 ms | 1316 KB |
03_long_07.txt | AC | 147 ms | 924 KB |
03_long_08.txt | AC | 145 ms | 928 KB |
03_long_09.txt | AC | 143 ms | 932 KB |
03_long_10.txt | AC | 143 ms | 928 KB |
03_long_11.txt | AC | 168 ms | 884 KB |
03_long_12.txt | AC | 142 ms | 5020 KB |
03_long_13.txt | AC | 146 ms | 928 KB |
03_long_14.txt | AC | 162 ms | 932 KB |
03_long_15.txt | AC | 179 ms | 924 KB |
03_long_16.txt | AC | 157 ms | 928 KB |
03_long_17.txt | AC | 137 ms | 924 KB |
03_long_18.txt | AC | 148 ms | 892 KB |
03_long_19.txt | AC | 139 ms | 800 KB |
04_manygroup_00.txt | AC | 174 ms | 936 KB |
04_manygroup_01.txt | AC | 177 ms | 932 KB |
04_manygroup_02.txt | AC | 142 ms | 928 KB |
04_manygroup_03.txt | AC | 149 ms | 932 KB |
04_manygroup_04.txt | AC | 168 ms | 928 KB |
04_manygroup_05.txt | AC | 162 ms | 928 KB |
04_manygroup_06.txt | AC | 149 ms | 920 KB |
04_manygroup_07.txt | AC | 146 ms | 928 KB |
04_manygroup_08.txt | AC | 143 ms | 940 KB |
04_manygroup_09.txt | AC | 140 ms | 800 KB |
04_manygroup_10.txt | AC | 175 ms | 932 KB |
04_manygroup_11.txt | AC | 172 ms | 932 KB |
04_manygroup_12.txt | AC | 172 ms | 936 KB |
04_manygroup_13.txt | AC | 163 ms | 928 KB |
04_manygroup_14.txt | AC | 169 ms | 932 KB |
04_manygroup_15.txt | AC | 174 ms | 932 KB |
04_manygroup_16.txt | AC | 176 ms | 928 KB |
04_manygroup_17.txt | AC | 154 ms | 928 KB |
04_manygroup_18.txt | AC | 184 ms | 936 KB |
04_manygroup_19.txt | AC | 176 ms | 928 KB |
10_min_01.txt | AC | 25 ms | 928 KB |
10_min_02.txt | AC | 25 ms | 924 KB |
10_min_03.txt | AC | 25 ms | 924 KB |