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
AC × 86
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