Submission #15869137
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define per(i, b) per2(i, 0, b)
#define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define ALL(c) (c).begin(), (c).end()
#define SZ(x) ((int)(x).size())
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T, class U>
void chmin(T& t, const U& u) {
if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
if (t < u) t = u;
}
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
os << "(" << p.first << "," << p.second << ")";
return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
os << "{";
rep(i, v.size()) {
if (i) os << ",";
os << v[i];
}
os << "}";
return os;
}
#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << H;
debug_out(T...);
}
#define debug(...) \
cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
const int maxn = 110;
const int maxs = 110;
constexpr ll INF = TEN(18);
int main() {
int N;
cin >> N;
V<string> S(N);
V<int> C(N);
map<string, int> sid;
sid[""] = 0; // goal
rep(i, N) {
cin >> S[i] >> C[i];
{
string t;
rep(j, S[i].size()) {
t.pb(S[i][j]);
if (!sid.count(t)) {
int sz = sid.size();
sid[t] = sz;
}
}
}
{
string t;
per(j, S[i].size()) {
t = S[i][j] + t;
if (!sid.count(t)) {
int sz = sid.size();
sid[t] = sz;
}
}
}
}
int sz = sid.size();
V<string> tos(sz);
V<bool> is_pal(sz);
for (auto p : sid) {
tos[p.se] = p.fi;
auto t = p.fi;
reverse(ALL(t));
is_pal[p.se] = (t == p.fi);
}
debug(tos);
VV<ll> d(2, V<ll>(sz, INF));
using Data = pair<ll, pii>; // cost, (direction, string id)
priority_queue<Data, V<Data>, greater<Data>> que;
ll ans = INF;
rep(i, N) {
{
auto t = S[i];
reverse(ALL(t));
if (S[i] == t) {
chmin(ans, C[i]);
continue;
}
}
int id = sid[S[i]];
rep(j, 2) {
if (d[j][id] > C[i]) {
d[j][id] = C[i];
que.push(mp(C[i], mp(j, id)));
}
}
}
while (!que.empty()) {
auto data = que.top();
que.pop();
int dir, id;
tie(dir, id) = data.se;
if (d[dir][id] < data.fi) continue;
// debug(d[dir][id], tos[id], dir);
rep(i, N) { // another side
string s = tos[id], t = S[i];
if (dir) swap(s, t); // s:left,t:right
int l = 0;
while (l < min(s.size(), t.size())) {
if (s[l] == t[t.size() - 1 - l]) {
l++;
} else {
break;
}
}
// NG
if (l < min(s.size(), t.size())) continue;
// debug(s, t, l);
ll nd = d[dir][id] + C[i];
if (l == s.size() && l == t.size()) {
chmin(ans, nd);
} else if (l == s.size()) {
string rem = t.substr(0, t.size() - l);
debug(rem);
int nid = sid[rem];
if (is_pal[nid]) chmin(ans, nd);
if (d[1][nid] > nd) {
d[1][nid] = nd;
que.push(mp(nd, mp(1, nid)));
}
} else {
string rem = s.substr(l, s.size() - l);
debug(rem);
int nid = sid[rem];
if (is_pal[nid]) chmin(ans, nd);
if (d[0][nid] > nd) {
d[0][nid] = nd;
que.push(mp(nd, mp(0, nid)));
}
}
}
}
if (ans == INF)
cout << -1 << endl;
else
cout << ans << endl;
return 0;
}
Submission Info
Submission Time
2020-08-13 22:24:48+0900
Task
F - Making Palindrome
User
satashun
Language
C++ (GCC 9.2.1)
Score
600
Code Size
4898 Byte
Status
AC
Exec Time
18 ms
Memory
3812 KiB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:17:41: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
17 | #define rep2(i, m, n) for (int i = m; i < (n); i++)
| ^
./Main.cpp:16:19: note: in expansion of macro ‘rep2’
16 | #define rep(i, n) rep2(i, 0, n)
| ^~~~
./Main.cpp:82:13: note: in expansion of macro ‘rep’
82 | rep(j, S[i].size()) {
| ^~~
./Main.cpp:155:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘const long unsigned int’ [-Wsign-compare]
155 | while (l < min(s.size(), t.size())) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
./Main.cpp:163:19: warning: comparison of integer expressions of different signedness: ‘int’ and ‘const long unsigned int’ [-Wsign-compare]
163 | if (l < min(s.size(), t.size())) continue;
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
./Main.cpp:167:19: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
167 | if (l == s.size() && l == t.size()) {
| ~~^~~~~~~~~~~
./Main.cpp:167:36: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
167 | if (l == s.size() && l == t.size()) {
| ~~^~~~~~~~~~~
./Main.cpp:169:26: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
169 | } else if (l == s.size()) {
| ~~^~~~~~~~~~~
Judge Result
Set Name
Sample
All
after_contest
Score / Max Score
0 / 0
600 / 600
0 / 0
Status
Set Name
Test Cases
Sample
s1.txt, s2.txt, s3.txt, s4.txt
All
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, after_contest_01.txt, s1.txt, s2.txt, s3.txt, s4.txt
after_contest
after_contest_01.txt
Case Name
Status
Exec Time
Memory
01.txt
AC 10 ms
3572 KiB
02.txt
AC 2 ms
3512 KiB
03.txt
AC 4 ms
3520 KiB
04.txt
AC 4 ms
3436 KiB
05.txt
AC 3 ms
3644 KiB
06.txt
AC 2 ms
3420 KiB
07.txt
AC 4 ms
3512 KiB
08.txt
AC 4 ms
3468 KiB
09.txt
AC 3 ms
3604 KiB
10.txt
AC 3 ms
3516 KiB
11.txt
AC 3 ms
3492 KiB
12.txt
AC 2 ms
3472 KiB
13.txt
AC 2 ms
3428 KiB
14.txt
AC 3 ms
3584 KiB
15.txt
AC 5 ms
3468 KiB
16.txt
AC 2 ms
3488 KiB
17.txt
AC 2 ms
3568 KiB
18.txt
AC 3 ms
3492 KiB
19.txt
AC 5 ms
3528 KiB
20.txt
AC 4 ms
3552 KiB
21.txt
AC 8 ms
3536 KiB
22.txt
AC 2 ms
3600 KiB
23.txt
AC 5 ms
3600 KiB
24.txt
AC 4 ms
3688 KiB
25.txt
AC 4 ms
3596 KiB
26.txt
AC 3 ms
3512 KiB
27.txt
AC 9 ms
3800 KiB
28.txt
AC 7 ms
3704 KiB
29.txt
AC 6 ms
3776 KiB
30.txt
AC 6 ms
3748 KiB
31.txt
AC 7 ms
3620 KiB
32.txt
AC 12 ms
3672 KiB
33.txt
AC 4 ms
3736 KiB
34.txt
AC 7 ms
3768 KiB
35.txt
AC 6 ms
3656 KiB
36.txt
AC 5 ms
3688 KiB
37.txt
AC 6 ms
3676 KiB
38.txt
AC 4 ms
3756 KiB
39.txt
AC 6 ms
3772 KiB
40.txt
AC 7 ms
3756 KiB
41.txt
AC 9 ms
3744 KiB
42.txt
AC 5 ms
3692 KiB
43.txt
AC 18 ms
3740 KiB
44.txt
AC 7 ms
3716 KiB
45.txt
AC 5 ms
3668 KiB
46.txt
AC 4 ms
3668 KiB
47.txt
AC 6 ms
3796 KiB
48.txt
AC 5 ms
3664 KiB
49.txt
AC 7 ms
3812 KiB
50.txt
AC 9 ms
3812 KiB
51.txt
AC 3 ms
3536 KiB
52.txt
AC 4 ms
3456 KiB
53.txt
AC 2 ms
3512 KiB
54.txt
AC 3 ms
3468 KiB
after_contest_01.txt
AC 5 ms
3496 KiB
s1.txt
AC 2 ms
3472 KiB
s2.txt
AC 3 ms
3564 KiB
s3.txt
AC 3 ms
3468 KiB
s4.txt
AC 2 ms
3500 KiB