結果

問題 No.517 壊れたアクセサリー
コンテスト
ユーザー tottoripaper
提出日時 2018-03-13 16:11:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,949 bytes
コンパイル時間 1,655 ms
コンパイル使用メモリ 169,176 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-22 05:45:48
合計ジャッジ時間 2,587 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:85:17: warning: 's' may be used uninitialized [-Wmaybe-uninitialized]
   85 |         while(s != -1){
      |               ~~^~~~~
main.cpp:69:13: note: 's' was declared here
   69 |         int s, terminal_n = 0;
      |             ^

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = long long;
using P = std::tuple<int,int>;

const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};

int N[2];
string S[2][26];
bool G[26][26];
int prv[2][26], nxt[2][26];

int main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    std::cin >> N[0];
    for(int i=0;i<N[0];++i){
        std::cin >> S[0][i];

        int l = S[0][i].size();
        for(int j=0;j+1<l;++j){
            G[S[0][i][j] - 'A'][S[0][i][j+1] - 'A'] = true;
        }
    }

    std::cin >> N[1];
    for(int i=0;i<N[1];++i){
        std::cin >> S[1][i];

        int l = S[1][i].size();
        for(int j=0;j+1<l;++j){
            G[S[1][i][j] - 'A'][S[1][i][j+1] - 'A'] = true;
        }        
    }

    for(int k=0;k<2;++k){
        for(int i=0;i<N[k];++i){
            nxt[k][i] = -1;
            prv[k][i] = -1;
        }
    }
    
    for(int k=0;k<2;++k){
        for(int i=0;i<N[k];++i){
            for(int j=0;j<N[k];++j){
                if(i == j){continue;}

                int a = *S[k][i].rbegin() - 'A',
                    b = *S[k][j].begin() - 'A';
                if(G[a][b]){
                    nxt[k][i] = j;
                    prv[k][j] = i;
                }
            }
        }
    }

    string res = "-1";
    for(int k=0;k<2;++k){
        int s, terminal_n = 0;

        for(int i=0;i<N[k];++i){
            if(nxt[k][i] == -1){
                terminal_n += 1;
            }
            if(prv[k][i] == -1){
                s = i; 
            }
        }
        
        if(terminal_n != 1){
            continue;
        }

        res = "";
        while(s != -1){
            res += S[k][s];
            s = nxt[k][s];
        }
    }

    std::cout << res << std::endl;
}
0