QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#645537#1193. Ambiguous EncodingxmbWA 1ms4168kbC++142.0kb2024-10-16 18:53:112024-10-16 18:53:13

Judging History

你现在查看的是最新测评结果

  • [2024-10-16 18:53:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4168kb
  • [2024-10-16 18:53:11]
  • 提交

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'