Submission #3928406

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);
}


string solve(int N, vs& a, vs& b) {
    vector<set<char>> dependency(128), rev(128);

    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;
        dependency[c2].insert(c1);
        rev[c1].insert(c2);
    }

    priority_queue<int, vi, greater<int>> pq;

    for (int c='a'; c<='z'; ++c) {
        if (dependency[c].empty()) pq.push(c);
    }

    vector<bool> visited(128, false);
    vector<char> res;

    while (!pq.empty()) {
        int c = pq.top(); pq.pop();
        if (visited[c]) return "-1";
        res.pb((char)c);
        visited[c] = true;
        for (char d: rev[c]) {
            dependency[d].erase(c);
            if (dependency[d].empty()) pq.push(d);
        }
    }
    if (res.size() != 26) return "-1";

    return string(ALL(res));
}

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 3260 Byte
Status
Exec Time 66 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 66 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 1 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 1 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 54 ms 2176 KB
50_random_02 60 ms 2432 KB
50_random_03 57 ms 2304 KB
50_random_04 52 ms 2048 KB
50_random_05 59 ms 2304 KB
50_random_06 50 ms 2048 KB
50_random_07 60 ms 2432 KB
50_random_08 51 ms 2048 KB
50_random_09 60 ms 2432 KB
51_random_00 60 ms 2432 KB
51_random_01 50 ms 2048 KB
51_random_02 52 ms 2176 KB