Submission #3928466


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#include <cassert>


typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<llll> vllll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define eb  emplace_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define repC3(vari,varj,vark,n)  for(int vari=0;vari<(n)-2;++vari)for(int varj=vari+1;varj<(n)-1;++varj)for(int vark=varj+1;vark<(n);++vark)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair

template<class T> inline void amin(T & a, T const & b) { a = min(a, b); }
template<class T> inline void amax(T & a, T const & b) { a = max(a, b); }
template<typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template<typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }


typedef pair<char,char> cc;

cc compare(string& s, string& t) {
    int sl = s.size(), tl = t.size(), ml = min(sl, tl);
    for (int i=0; i<ml; ++i) {
        if (s[i] == t[i]) continue;
        if (s[i] != t[i]) {
            return cc(s[i], t[i]);
        }
    }
    if (sl <= tl) return cc(0,0);
    else return cc(-1,-1);
}

template <typename T>
vector<T> toposort(const set<T> group, const set<pair<T,T>>& arcs) {
    map<T, set<T>> from, to;
    for (pair<T,T> arc: arcs) {
        T u = arc.first, v = arc.second;
        from[u].insert(v);
        to[v].insert(u);
    }
    int E = arcs.size();

    set<T> S;
    for (T i : group) {
        if (!found(to, i)) S.insert(i);
    }

    vector<T> L;
    while (!S.empty()) {
        T u = *S.begin();
        S.erase(u);
        L.push_back(u);
        for (T v: from[u]) {
            to[v].erase(u);
            --E;
            if (to[v].empty()) {
                S.insert(v);
            }
        }
    }

    if (E != 0) {
        return vector<T> {};
    }

    return L;
}

string solve(int N, vs& a, vs& b) {
    set<char> group;
    set<cc> arcs;

    rep(i,N){
        cc c = compare(a[i], b[i]);
        if (c.first == -1) return "-1";
        else if (c.first == 0) continue;

        char c1 = c.first, c2 = c.second;
        group.insert(c1);
        group.insert(c2);
        arcs.insert(cc((char)'0', c1));
        arcs.insert(c);
    }

    for (char i='a'; i<='z'; ++i) {
        if (!found(group, i)) {
            group.insert(i);
            arcs.insert(cc((char)'0', i));
        }
    }
    group.insert('0');

    vector<char> t = toposort(group, arcs);
    if (t.empty()) return "-1";
    return string(t.begin()+1, t.end());
}

int main() {
    int N; cin >> N;
    vs a(N), b(N);
    rep(i,N){
        cin >> a[i] >> b[i];
    }
    cout << solve(N,a,b) << endl;
    return 0;
}

Submission Info

Submission Time
Task C - 山田山本問題
User naoya_t
Language C++14 (GCC 5.4.1)
Score 600
Code Size 3787 Byte
Status
Exec Time 67 ms
Memory 2432 KB

Test Cases

Set Name Score / Max Score Test Cases
All 600 / 600 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 01_manual_00, 01_manual_01, 01_manual_02, 01_manual_03, 01_manual_04, 01_manual_05, 01_manual_06, 01_manual_07, 10_random_00, 10_random_01, 10_random_02, 10_random_03, 10_random_04, 10_random_05, 10_random_06, 10_random_07, 10_random_08, 10_random_09, 30_random_00, 30_random_01, 30_random_02, 30_random_03, 30_random_04, 30_random_05, 30_random_06, 30_random_07, 30_random_08, 30_random_09, 50_random_00, 50_random_01, 50_random_02, 50_random_03, 50_random_04, 50_random_05, 50_random_06, 50_random_07, 50_random_08, 50_random_09, 51_random_00, 51_random_01, 51_random_02
Case Name Status Exec Time Memory
00_sample_01 1 ms 256 KB
00_sample_02 1 ms 256 KB
00_sample_03 1 ms 256 KB
00_sample_04 1 ms 256 KB
01_manual_00 1 ms 256 KB
01_manual_01 1 ms 256 KB
01_manual_02 1 ms 256 KB
01_manual_03 1 ms 256 KB
01_manual_04 1 ms 256 KB
01_manual_05 1 ms 256 KB
01_manual_06 1 ms 256 KB
01_manual_07 67 ms 2304 KB
10_random_00 2 ms 256 KB
10_random_01 2 ms 256 KB
10_random_02 2 ms 256 KB
10_random_03 2 ms 256 KB
10_random_04 2 ms 256 KB
10_random_05 2 ms 256 KB
10_random_06 2 ms 256 KB
10_random_07 2 ms 256 KB
10_random_08 1 ms 256 KB
10_random_09 2 ms 256 KB
30_random_00 2 ms 256 KB
30_random_01 2 ms 256 KB
30_random_02 1 ms 256 KB
30_random_03 1 ms 256 KB
30_random_04 2 ms 256 KB
30_random_05 2 ms 256 KB
30_random_06 1 ms 256 KB
30_random_07 2 ms 256 KB
30_random_08 2 ms 256 KB
30_random_09 2 ms 256 KB
50_random_00 56 ms 2176 KB
50_random_01 55 ms 2176 KB
50_random_02 61 ms 2432 KB
50_random_03 57 ms 2304 KB
50_random_04 52 ms 2048 KB
50_random_05 60 ms 2304 KB
50_random_06 51 ms 2048 KB
50_random_07 61 ms 2432 KB
50_random_08 52 ms 2048 KB
50_random_09 60 ms 2432 KB
51_random_00 60 ms 2304 KB
51_random_01 51 ms 2048 KB
51_random_02 53 ms 2048 KB