Submission #3589272


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<P<int, string>> cost(2 * 100000 + 10,{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,"" };
	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[idx_to].first) || (cost_to == cost[idx_to].first && str_to < cost[idx_to].second)) {
				cost[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();

	cout << cost[N - 1].second << endl;
	cin >> N;
	return 0;
}

Submission Info

Submission Time
Task E - Don't Be a Subsequence
User ningenMe
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3712 Byte
Status TLE
Exec Time 2171 ms
Memory 1086704 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 3
AC × 19
TLE × 3
MLE × 14
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
1.txt AC 12 ms 23792 KB
10.txt MLE 830 ms 327024 KB
11.txt MLE 832 ms 325232 KB
12.txt MLE 818 ms 319088 KB
13.txt MLE 829 ms 324336 KB
14.txt MLE 923 ms 320624 KB
15.txt MLE 829 ms 323312 KB
16.txt MLE 832 ms 324976 KB
17.txt MLE 1091 ms 555760 KB
18.txt MLE 1219 ms 639984 KB
19.txt MLE 1529 ms 828400 KB
2.txt AC 14 ms 23792 KB
20.txt MLE 1954 ms 1049840 KB
21.txt TLE 2020 ms 1072880 KB
22.txt TLE 2046 ms 1086704 KB
23.txt TLE 2171 ms 1057264 KB
24.txt AC 616 ms 129392 KB
25.txt AC 512 ms 50800 KB
26.txt AC 617 ms 90608 KB
27.txt AC 522 ms 58992 KB
28.txt AC 530 ms 65136 KB
29.txt AC 605 ms 138736 KB
3.txt AC 34 ms 24944 KB
30.txt AC 606 ms 133872 KB
4.txt AC 37 ms 24944 KB
5.txt AC 329 ms 100848 KB
6.txt AC 334 ms 101104 KB
7.txt MLE 834 ms 331376 KB
8.txt MLE 836 ms 324208 KB
9.txt MLE 834 ms 327024 KB
sample1.txt AC 12 ms 23792 KB
sample2.txt AC 12 ms 23792 KB
sample3.txt AC 13 ms 23792 KB