QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#645537 | #1193. Ambiguous Encoding | xmb | WA | 1ms | 4168kb | C++14 | 2.0kb | 2024-10-16 18:53:11 | 2024-10-16 18:53:13 |
Judging History
answer
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 55;
const int maxm = 2510;
int n, id[maxn][maxn], nt, f[maxm];
bool vis[maxm];
vector<pii> G[maxm];
string s[maxn];
struct node {
int u, d;
node(int a = 0, int b = 0) : u(a), d(b) {}
};
inline bool operator < (const node &a, const node &b) {
return a.d > b.d;
}
priority_queue<node> pq;
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
cin >> s[i];
for (int j = 0; j < (int)s[i].size(); ++j) {
id[i][j] = ++nt;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < (int)s[i].size(); ++j) {
for (int k = 1; k <= n; ++k) {
int t = min(j, (int)s[k].size());
if (s[k].substr(0, t) == s[i].substr((int)s[i].size() - j, t)) {
if (t == (int)s[k].size()) {
G[id[i][j]].pb(id[i][j - t], t);
} else {
G[id[i][j]].pb(id[k][(int)s[k].size() - j], t);
}
}
}
}
}
mems(f, 0x3f);
set<string> S;
for (int i = 1; i <= n; ++i) {
S.insert(s[i]);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < (int)s[i].size(); ++j) {
string t = s[i].substr(0, j);
if (S.find(t) != S.end()) {
f[id[i][(int)s[i].size() - j]] = j;
pq.emplace(id[i][(int)s[i].size() - j], j);
}
}
}
while (pq.size()) {
int u = pq.top().u;
pq.pop();
if (vis[u]) {
continue;
}
vis[u] = 1;
for (pii p : G[u]) {
int v = p.fst, d = p.scd;
if (f[v] > f[u] + d) {
f[v] = f[u] + d;
if (!vis[v]) {
pq.emplace(v, f[v]);
}
}
}
}
int ans = 2e9;
for (int i = 1; i <= n; ++i) {
ans = min(ans, f[id[i][0]]);
}
printf("%d\n", ans > 1e9 ? -1 : ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4168kb
input:
3 0 01 10
output:
3
result:
ok answer is '3'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3884kb
input:
3 00 01 1
output:
-1
result:
wrong answer expected '0', found '-1'