Submission #3589230

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string> 
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

#define REP(i,n) for(int i = 0; i < int(n); i++)
#define FOR(i, m, n) for(int i = int(m);i < int(n);i++)
#define ALL(obj) (obj).begin(),(obj).end()

const ll MOD = (ll)1e9 + 7;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;

vector<int> dy = { 0,0,1,-1 };
vector<int> dx = { 1,-1,0,0 };

template<class T> void corner(bool flg, T hoge) {
	if (flg) {
		cout << hoge << endl;
		exit(0);
	}
	else return;
}

template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {
	o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;
}

template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {
	o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}

template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {
	o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;
}

template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {
	o << "{" << obj.first << ", " << obj.second << "}"; return o;
}

template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {
	o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}

void print(void) {
	cout << endl;
}

template <class Head> void print(Head&& head) {
	cout << head;
	print();
}

template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {
	cout << head << " ";
	print(forward<Tail>(tail)...);
}

void YN(bool flg) {
	cout << ((flg) ? "YES" : "NO") << endl;
}

void Yn(bool flg) {
	cout << ((flg) ? "Yes" : "No") << endl;
}

void yn(bool flg) {
	cout << ((flg) ? "yes" : "no") << endl;
}

V<V< int >> edge(26, V< int >(2 * 100000 + 10));
V<V<P<int, string>>> cost(26,V<P<int,string>>(2 * 100000 + 1,{LINF,""}));
int N;

void Dijkstra() {
	priority_queue<P<P<int, string>, P<int, int>>, V<P<P<int, string>, P<int, int>>>, greater<P<P<int, string>, P<int, int>>>> pq;
	cost[0][0] = { 0,"" };
	pq.push({ {0,""},{0,0} });
	while(!pq.empty()){
		int cost_from = pq.top().first.first;
		string str_from = pq.top().first.second;
		int alp_from = pq.top().second.first;
		int idx_from = pq.top().second.second;
		pq.pop();
		if (idx_from == N - 1) continue;

		REP(i, 26) {
			int cost_to, alp_to, idx_to;
			string str_to;
			char ch = char(int(i + 'a'));
			cost_to = cost_from + 1;
			alp_to = i;
			idx_to = edge[i][idx_from];
			str_to = str_from;
			str_to.push_back(ch);

			if ((cost_to < cost[alp_to][idx_to].first) || (cost_to == cost[alp_to][idx_to].first && str_to < cost[alp_to][idx_to].second)) {
				cost[alp_to][idx_to] = { cost_to,str_to };
				pq.push({ {cost_to,str_to},{alp_to,idx_to} });
			}
		}
	}
	return;
}

int main() {
	string s; cin >> s;
	s = "." + s + ".";
	N = s.size();
	REP(i,26){
		char ch = char(int(i + 'a'));
		int idx = N-1;
		for (int j = N-2; 0 <= j; --j) {
			edge[i][j] = idx;
			if (s[j] == ch)idx = j;
		}
	}
	Dijkstra();

	map<int, V<string>> mp;
	REP(i, 26) mp[cost[i][N - 1].first].push_back(cost[i][N - 1].second);
	for(auto u:mp){
		sort(ALL(u.second));
		cout << u.second[0] << endl;
		return 0;
	}
	return 0;
}

Submission Info

Judge Result