Submission #15980954


Source Code Expand

Copy
#include <bits/stdc++.h>
using Int = long long;  // clang-format off
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define ALL(v) std::begin(v), std::end(v)
#define RALL(v) std::rbegin(v), std::rend(v)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sat Aug 15 22:15:43 JST 2020
 **/

template <class T> bool chmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <class T> bool chmax(T& a, const T& b) { return a < b ? a = b, true : false; }

template <class T, class S> T make_vec(S x) { return x; }
template <class T, class... Ts> auto make_vec(size_t n, Ts... ts) {
    return std::vector<decltype(make_vec<T>(ts...))>(n, make_vec<T>(ts...));
}

template <class Dist, class Key, class Delta>  // Delta: Key from, (Key to, Dist d -> void) update -> void
std::map<Key, Dist> dijkstra(Key s, Delta delta) {
    std::map<Key, Dist> dist;
    using P = std::pair<Dist, Key>;
    std::priority_queue<P, std::vector<P>, std::greater<P>> q;
    q.push({dist[s] = Dist(), s});
    while (!q.empty()) {
        std::pair<Dist, Key> p = q.top();
        q.pop();
        if (dist[p.second] < p.first) continue;
        delta(p.second, [&](Key to, Dist d) -> void {
            if (dist.count(to) && dist[to] <= p.first + d) return;
            q.push({dist[to] = p.first + d, to});
        });
    }
    return dist;
}

bool is_palindrome(const std::string& s) { return s == std::string(s.rbegin(), s.rend()); }
const Int INF = 1e18;
const std::string dummy = "01";
signed main() {
    Int n;
    std::cin >> n;
    auto ss = make_vec<std::string>(2, n, "");
    std::vector<Int> c(n);
    REP(i, n) std::cin >> ss[0][i] >> c[i], ss[1][i] = std::string(RALL(ss[0][i]));
    using Key = std::pair<std::string, bool>;
    auto delta = [&](Key from, auto update) -> void {
        REP(i, n) {
            std::string s = from.first == dummy ? "" : from.first;
            std::string t = ss[!from.second][i];
            bool nxt_b = from.second ^ (s.size() < t.size());
            if (s > t) std::swap(s, t);
            if (s != t.substr(0, s.size())) continue;
            std::string nxt_s = t.substr(s.size(), t.size() - s.size());
            update(Key{nxt_s, nxt_b}, c[i]);
        }
    };
    Key s = {dummy, 0};
    auto res = dijkstra<Int>(s, delta);
    Int ans = INF;
    for (auto& p : res) {
        if (is_palindrome(p.first.first)) chmin(ans, p.second);
    }
    std::cout << (ans == INF ? -1 : ans) << std::endl;
}

Submission Info

Submission Time
Task F - Making Palindrome
User knshnb
Language C++ (GCC 9.2.1)
Score 600
Code Size 2754 Byte
Status
Exec Time 17 ms
Memory 3784 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt, s4.txt
All 600 / 600 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 0 / 0 after_contest_01.txt
Case Name Status Exec Time Memory
01.txt 6 ms 3476 KB
02.txt 2 ms 3596 KB
03.txt 4 ms 3568 KB
04.txt 12 ms 3620 KB
05.txt 2 ms 3544 KB
06.txt 2 ms 3608 KB
07.txt 2 ms 3628 KB
08.txt 3 ms 3532 KB
09.txt 2 ms 3644 KB
10.txt 2 ms 3600 KB
11.txt 3 ms 3692 KB
12.txt 2 ms 3640 KB
13.txt 3 ms 3532 KB
14.txt 2 ms 3684 KB
15.txt 2 ms 3632 KB
16.txt 3 ms 3520 KB
17.txt 3 ms 3596 KB
18.txt 2 ms 3544 KB
19.txt 3 ms 3648 KB
20.txt 4 ms 3628 KB
21.txt 5 ms 3696 KB
22.txt 3 ms 3636 KB
23.txt 4 ms 3704 KB
24.txt 4 ms 3632 KB
25.txt 4 ms 3504 KB
26.txt 11 ms 3628 KB
27.txt 5 ms 3648 KB
28.txt 8 ms 3708 KB
29.txt 4 ms 3676 KB
30.txt 4 ms 3676 KB
31.txt 2 ms 3668 KB
32.txt 3 ms 3700 KB
33.txt 3 ms 3556 KB
34.txt 3 ms 3704 KB
35.txt 4 ms 3672 KB
36.txt 4 ms 3696 KB
37.txt 4 ms 3620 KB
38.txt 9 ms 3628 KB
39.txt 6 ms 3604 KB
40.txt 5 ms 3620 KB
41.txt 3 ms 3656 KB
42.txt 4 ms 3672 KB
43.txt 17 ms 3784 KB
44.txt 17 ms 3624 KB
45.txt 6 ms 3632 KB
46.txt 4 ms 3672 KB
47.txt 4 ms 3680 KB
48.txt 6 ms 3616 KB
49.txt 4 ms 3636 KB
50.txt 3 ms 3636 KB
51.txt 2 ms 3616 KB
52.txt 4 ms 3616 KB
53.txt 2 ms 3632 KB
54.txt 2 ms 3536 KB
after_contest_01.txt 2 ms 3628 KB
s1.txt 2 ms 3640 KB
s2.txt 2 ms 3680 KB
s3.txt 7 ms 3648 KB
s4.txt 3 ms 3524 KB