Submission #6535492
Source Code Expand
#include<bits/stdc++.h> using namespace std; using ll = long long; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } #define FOR(i,a,b) for(ll i=(a);i<(b);++i) #define ALL(v) (v).begin(), (v).end() #define p(s) cout<<(s)<<endl #define p2(s, t) cout << (s) << " " << (t) << endl #define br() p("") #define pn(s) cout << (#s) << " " << (s) << endl const ll mod = 1e9 + 7; const ll inf = 1e18; ll dist(string s, string t){ ll L = s.size(); ll ret = s.size(); FOR(i, 0, L){ if(s[i]==t[i]) ret--; } return ret; } vector<vector<ll>> G; int main(){ cin.tie(0); ios::sync_with_stdio(false); // input string first, last; cin >> first >> last; if(first==last){ p(0); p(first); p(last); return 0; } ll N; cin >> N; vector<string> W; W.push_back(first); FOR(i, 0, N){ string word; cin >> word; W.push_back(word); } W.push_back(last); N+=2; G.resize(N); vector<ll> d(1005, inf); FOR(i, 0, N){ FOR(j, i+1, N){ if(dist(W[i], W[j])==1){ // edge G[i].push_back(j); G[j].push_back(i); } } } // bfs queue<ll> que; que.push(0); d[0]=0; while(!que.empty()){ ll i = que.front(); que.pop(); for(ll to : G[i]){ if(d[to]==inf){ d[to] = d[i]+1; que.push(to); } } } if(d[N-1]==inf){ p(-1); return 0; } // N-1から逆向きにたどる vector<string> Ans; Ans.push_back(last); ll current = N-1; ll D = d[N-1]; while(D>0){ for(ll to : G[current]){ if(d[to]==D-1){ // そこにいく Ans.push_back(W[to]); D--; current = to; break; } } } reverse(ALL(Ans)); p(Ans.size()-2); for(string w : Ans){ p(w); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - ダブレット |
User | peroon |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2177 Byte |
Status | AC |
Exec Time | 89 ms |
Memory | 8832 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 | 1 ms | 256 KB |
00_sample_02.txt | AC | 1 ms | 256 KB |
00_sample_03.txt | AC | 1 ms | 256 KB |
01_rand_00.txt | AC | 80 ms | 384 KB |
01_rand_01.txt | AC | 3 ms | 256 KB |
01_rand_02.txt | AC | 63 ms | 384 KB |
01_rand_03.txt | AC | 5 ms | 768 KB |
01_rand_04.txt | AC | 28 ms | 384 KB |
01_rand_05.txt | AC | 1 ms | 256 KB |
01_rand_06.txt | AC | 28 ms | 384 KB |
01_rand_07.txt | AC | 15 ms | 384 KB |
01_rand_08.txt | AC | 4 ms | 256 KB |
01_rand_09.txt | AC | 16 ms | 384 KB |
01_rand_10.txt | AC | 55 ms | 384 KB |
01_rand_11.txt | AC | 87 ms | 384 KB |
01_rand_12.txt | AC | 36 ms | 384 KB |
01_rand_13.txt | AC | 78 ms | 384 KB |
01_rand_14.txt | AC | 60 ms | 8448 KB |
01_rand_15.txt | AC | 16 ms | 384 KB |
01_rand_16.txt | AC | 51 ms | 7808 KB |
01_rand_17.txt | AC | 32 ms | 384 KB |
01_rand_18.txt | AC | 2 ms | 256 KB |
01_rand_19.txt | AC | 54 ms | 384 KB |
02_maxrand_00.txt | AC | 84 ms | 384 KB |
02_maxrand_01.txt | AC | 87 ms | 384 KB |
02_maxrand_02.txt | AC | 65 ms | 8832 KB |
02_maxrand_03.txt | AC | 89 ms | 384 KB |
02_maxrand_04.txt | AC | 67 ms | 384 KB |
02_maxrand_05.txt | AC | 81 ms | 384 KB |
02_maxrand_06.txt | AC | 86 ms | 384 KB |
02_maxrand_07.txt | AC | 87 ms | 384 KB |
02_maxrand_08.txt | AC | 89 ms | 384 KB |
02_maxrand_09.txt | AC | 81 ms | 384 KB |
02_maxrand_10.txt | AC | 88 ms | 384 KB |
02_maxrand_11.txt | AC | 82 ms | 512 KB |
02_maxrand_12.txt | AC | 84 ms | 384 KB |
02_maxrand_13.txt | AC | 81 ms | 384 KB |
02_maxrand_14.txt | AC | 81 ms | 384 KB |
02_maxrand_15.txt | AC | 84 ms | 384 KB |
02_maxrand_16.txt | AC | 88 ms | 384 KB |
02_maxrand_17.txt | AC | 63 ms | 1408 KB |
02_maxrand_18.txt | AC | 81 ms | 384 KB |
02_maxrand_19.txt | AC | 65 ms | 512 KB |
03_long_00.txt | AC | 86 ms | 384 KB |
03_long_01.txt | AC | 83 ms | 384 KB |
03_long_02.txt | AC | 67 ms | 384 KB |
03_long_03.txt | AC | 67 ms | 384 KB |
03_long_04.txt | AC | 77 ms | 384 KB |
03_long_05.txt | AC | 72 ms | 384 KB |
03_long_06.txt | AC | 63 ms | 1408 KB |
03_long_07.txt | AC | 75 ms | 384 KB |
03_long_08.txt | AC | 74 ms | 384 KB |
03_long_09.txt | AC | 73 ms | 384 KB |
03_long_10.txt | AC | 71 ms | 384 KB |
03_long_11.txt | AC | 85 ms | 384 KB |
03_long_12.txt | AC | 65 ms | 8832 KB |
03_long_13.txt | AC | 63 ms | 512 KB |
03_long_14.txt | AC | 82 ms | 384 KB |
03_long_15.txt | AC | 85 ms | 384 KB |
03_long_16.txt | AC | 78 ms | 384 KB |
03_long_17.txt | AC | 67 ms | 384 KB |
03_long_18.txt | AC | 67 ms | 384 KB |
03_long_19.txt | AC | 70 ms | 384 KB |
04_manygroup_00.txt | AC | 85 ms | 384 KB |
04_manygroup_01.txt | AC | 88 ms | 384 KB |
04_manygroup_02.txt | AC | 73 ms | 384 KB |
04_manygroup_03.txt | AC | 76 ms | 384 KB |
04_manygroup_04.txt | AC | 81 ms | 384 KB |
04_manygroup_05.txt | AC | 81 ms | 384 KB |
04_manygroup_06.txt | AC | 68 ms | 384 KB |
04_manygroup_07.txt | AC | 76 ms | 384 KB |
04_manygroup_08.txt | AC | 73 ms | 384 KB |
04_manygroup_09.txt | AC | 70 ms | 384 KB |
04_manygroup_10.txt | AC | 88 ms | 384 KB |
04_manygroup_11.txt | AC | 86 ms | 384 KB |
04_manygroup_12.txt | AC | 85 ms | 384 KB |
04_manygroup_13.txt | AC | 81 ms | 384 KB |
04_manygroup_14.txt | AC | 85 ms | 384 KB |
04_manygroup_15.txt | AC | 88 ms | 384 KB |
04_manygroup_16.txt | AC | 88 ms | 384 KB |
04_manygroup_17.txt | AC | 77 ms | 384 KB |
04_manygroup_18.txt | AC | 89 ms | 384 KB |
04_manygroup_19.txt | AC | 88 ms | 384 KB |
10_min_01.txt | AC | 1 ms | 256 KB |
10_min_02.txt | AC | 1 ms | 256 KB |
10_min_03.txt | AC | 1 ms | 256 KB |