Submission #822791


Source Code Expand

Copy
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

string A[1010];
string B[1010];
vector<int> G[26];
int inComing[26];

int main(){
  int N;
  cin>>N;
  for(int i=0;i<N;i++){
    cin>>A[i]>>B[i];
  }
  for(int i=0;i<N;i++){
    int size = min(A[i].size(),B[i].size());
    int j;
    for(j=0;j<size;j++){
      if(A[i][j] != B[i][j]){
	G[A[i][j]-'a'].push_back(B[i][j]-'a');
	inComing[B[i][j]-'a']++;
	break;
      }
    }
    if(j == size && A[i].size() > B[i].size()){
      cout<<-1<<endl;
      return 0;
    }
  }
  priority_queue<int,vector<int>,greater<int> > pq;
  for(int i=0;i<26;i++){
    if(inComing[i] == 0) pq.push(i);
  }
  string ans = "";
  while(pq.size()){
    int v = pq.top();
    pq.pop();
    ans += string(1,v+'a');
    for(int i=0;i<G[v].size();i++){
      int w = G[v][i];
      inComing[w]--;
      if(inComing[w] == 0){
	pq.push(w);
      }
    }
  }
  if(ans.size() == 26){
    cout<<ans<<endl;
  }else{
    cout<<-1<<endl;
  }
  return 0;
}

Submission Info

Submission Time
Task C - 山田山本問題
User commy
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1089 Byte
Status
Exec Time 122 ms
Memory 2304 KB

Judge Result

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 4 ms 256 KB
00_sample_02 4 ms 256 KB
00_sample_03 4 ms 256 KB
00_sample_04 4 ms 256 KB
01_manual_00 4 ms 256 KB
01_manual_01 4 ms 256 KB
01_manual_02 4 ms 256 KB
01_manual_03 4 ms 256 KB
01_manual_04 4 ms 256 KB
01_manual_05 4 ms 256 KB
01_manual_06 4 ms 256 KB
01_manual_07 122 ms 2304 KB
10_random_00 4 ms 256 KB
10_random_01 5 ms 256 KB
10_random_02 5 ms 256 KB
10_random_03 4 ms 256 KB
10_random_04 5 ms 256 KB
10_random_05 5 ms 256 KB
10_random_06 4 ms 256 KB
10_random_07 5 ms 256 KB
10_random_08 4 ms 256 KB
10_random_09 4 ms 256 KB
30_random_00 4 ms 256 KB
30_random_01 4 ms 256 KB
30_random_02 4 ms 256 KB
30_random_03 4 ms 256 KB
30_random_04 4 ms 256 KB
30_random_05 4 ms 256 KB
30_random_06 4 ms 256 KB
30_random_07 4 ms 256 KB
30_random_08 4 ms 256 KB
30_random_09 5 ms 256 KB
50_random_00 104 ms 2176 KB
50_random_01 101 ms 2176 KB
50_random_02 112 ms 2304 KB
50_random_03 104 ms 2176 KB
50_random_04 97 ms 2048 KB
50_random_05 109 ms 2304 KB
50_random_06 92 ms 2048 KB
50_random_07 111 ms 2304 KB
50_random_08 94 ms 2048 KB
50_random_09 109 ms 2304 KB
51_random_00 110 ms 2304 KB
51_random_01 92 ms 2048 KB
51_random_02 98 ms 2048 KB