QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#759734 | #9558. The Devil | IllusionaryDominance | ML | 2352ms | 485560kb | C++20 | 5.0kb | 2024-11-18 11:36:41 | 2024-11-18 11:36:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef vector <int> vi;
const int MAX_N = 130;
const int MAX_M = 1 << 23;
const int MAX_V = 1 << 15;
const int MAX_E = 1 << 17;
const int INF32 = 0x3f3f3f3f;
int N, s, t;
struct TrieNode{
int son[52], dep;
}node[MAX_M];
int pool[MAX_M], poolSize;
int tot, cur[MAX_N], cnt, idx[MAX_M], w[MAX_V], M;
struct Edge{
int y, prev, cap, cost;
}e[MAX_E];
int elast[MAX_V], ecnt = 1;
int dis[MAX_V], pre[MAX_V], flow;
char inq[MAX_V], vis[MAX_M];
string ans[MAX_N], pat[MAX_V];
inline int NewNode() {
if (poolSize) {
return pool[-- poolSize];
}
return ++ tot;
}
inline void delNode(int nd) {
pool[poolSize ++] = nd;
node[nd].dep = 0;
memset(node[nd].son, 0, sizeof node[nd].son);
}
void Build(int x, int y, int z, int c) {
ecnt ++;
e[ecnt].y = y;
e[ecnt].cap = z;
e[ecnt].cost = c;
e[ecnt].prev = elast[x];
elast[x] = ecnt;
}
void add_edge(int x, int y, int z, int c) {
Build(x, y, z, c); Build(y, x, 0, -c);
}
bool spfa() {
queue <int> q;
memset(dis, 0x3f, sizeof(int) * (t + 1));
q.push(s); dis[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop(); inq[u] = 0;
for (int i = elast[u]; i; i = e[i].prev) {
int v = e[i].y;
if (e[i].cap && dis[u] + e[i].cost < dis[v]) {
pre[v] = i;
dis[v] = dis[u] + e[i].cost;
if (!inq[v]) {
inq[v] = 1; q.push(v);
}
}
}
}
if (dis[t] >= INF32) return false;
int f = N;
for (int v = t; v != s; v = e[pre[v] ^ 1].y) f = min(f, e[pre[v]].cap);
for (int v = t; v != s; v = e[pre[v] ^ 1].y) {
e[pre[v]].cap -= f;
e[pre[v] ^ 1].cap += f;
}
flow += f;
return true;
}
vi ins(const vi &s, int u) {
vi res(min((int)s.size(), N));
for (int i = 0; i < (int)s.size() && i < N; i ++) {
int &v = node[u].son[s[i]];
if (!v) {
v = ++ tot;
node[v].dep = node[u].dep + 1;
}
res[i] = v; u = v;
}
return res;
}
vi Merge(const vi &a, const vi &b) {
vi c(0);
for (auto i = a.begin(), j = b.begin(); (int)c.size() < N; ) {
while (i != a.end() && vis[*i]) i ++;
while (j != b.end() && vis[*j]) j ++;
if (i == a.end() && j == b.end()) break;
if (j == b.end() || (i != a.end() && node[*i].dep < node[*j].dep)) {
c.push_back(*(i ++));
}else {
c.push_back(*(j ++));
}
vis[c.back()] = 1;
}
for (auto x : c) vis[x] = 0;
return c;
}
void ins(const vi &s) {
vi a(0);
for (int i = 1; i <= cnt; i ++) {
vi b = ins(s, cur[i]);
a = Merge(a, b);
}
cnt = a.size();
for (int i = 1; i <= cnt; i ++) {
cur[i] = a[i - 1];
}
}
bool dfs(int u) {
bool res = false;
for (int i = 0; i < 52; i ++) {
if (node[u].son[i]) {
bool fv = dfs(node[u].son[i]);
res = res || fv;
if (!fv) node[u].son[i] = 0;
}
}
res = res || idx[u];
if (!res) delNode(u);
return res;
}
void dfs(int u, string &s) {
if (idx[u]) {
pat[idx[u]] = s;
}
for (int i = 0; i < 52; i ++) {
if (node[u].son[i]) {
s.push_back((char)(i < 26 ? i + 'A' : i - 26 + 'a'));
dfs(node[u].son[i], s);
s.pop_back();
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> N;
string trash;
getline(cin, trash);
for (int i = 1; i <= N; i ++) {
vi s;
string t;
getline(cin, t);
cur[cnt = 1] = 0;
for (int j = 0, k; j < (int)t.size(); j ++) {
for (k = j; k < (int)t.size() && t[k] != ' '; k ++);
s.resize(k - j);
auto it = s.begin();
while (j < k) {
*it = t[j] <= 'Z' ? t[j] - 'A' : t[j] - 'a' + 26;
j ++; it ++;
}
assert(it == s.end());
ins(s);
}
assert(cnt <= N);
for (int j = 1; j <= cnt; j ++) {
if (!idx[cur[j]]) {
idx[cur[j]] = ++ M;
w[M] = node[cur[j]].dep;
}
add_edge(i, N + idx[cur[j]], 1, 0);
}
if ((i & 7) == 1) dfs(0);
}
string sta;
dfs(0, sta);
s = M + N + 1; t = s + 1;
for (int i = 1; i <= N; i ++) {
add_edge(s, i, 1, 0);
}
for (int i = 1; i <= M; i ++) {
add_edge(i + N, t, 1, w[i]);
}
while (spfa());
if (flow < N) {
cout << "no solution\n";
return 0;
}
for (int i = 2; i <= ecnt; i += 2) {
auto [y, trash1, cap, trash2] = e[i];
auto [x, trash3, rcap, trash4] = e[i ^ 1];
if (x <= N && rcap) {
ans[x] = pat[y - N];
}
}
for (int i = 1; i <= N; i ++) {
cout << ans[i] << '\n';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 10484kb
input:
5 automated teller machine active teller machine active trouble maker always telling misinformation American Teller Machinery
output:
autm actm atma atm ATM
result:
ok len=18
Test #2:
score: 0
Accepted
time: 0ms
memory: 10948kb
input:
5 Forest Conservation Committee Forum Fuming Corruption Collusion Federation Fulsome Cash Concealment Foundation Funky Crony Capitalism Facilitator Funny Cocky Cocky Funny
output:
FCoCF FCCFe FCCFo FCCFa FCCF
result:
ok len=24
Test #3:
score: 0
Accepted
time: 1ms
memory: 10768kb
input:
3 A AA AA A A A A
output:
no solution
result:
ok len=-1
Test #4:
score: 0
Accepted
time: 1ms
memory: 10936kb
input:
2 QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnmertyuiop Q W E R T Y U I O P A S D F G H J K L Z X C V B N M q w e r t y u i o p a s d f g h j k l z x c v b n m j k l z x c v b n m
output:
Q QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnmjklzxcvbnm
result:
ok len=63
Test #5:
score: 0
Accepted
time: 1ms
memory: 10624kb
input:
10 aaa aaa aaa aaa aaa aaa aab aaa aaa aaa aaa aaa aaa aab aaa aaa aaa aaa aab aab aaa aaa aaa aaa a a a a a a ab ab a a a a a a ab ab b a a a a a a aw a a a a a az az a a a a az a a a a a
output:
aaaaaaaaa aabaaaaa aaabaaaa aaaaaaa aaaaaa aaaaaaaa aabaaaaaa awaaaaa aazaaaa azaaaaa
result:
ok len=76
Test #6:
score: 0
Accepted
time: 1963ms
memory: 11616kb
input:
128 zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
result:
ok len=24512
Test #7:
score: 0
Accepted
time: 2083ms
memory: 201600kb
input:
128 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaae aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaar aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb cccccccccccccccccccccccccccccccccccccccccc...
result:
ok len=16534
Test #8:
score: 0
Accepted
time: 2339ms
memory: 68268kb
input:
128 zAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
zAAAAAAAAAAAAAAAzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz zAAAAAAAAAAAAAAzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz zAAAAAAAAAAA...
result:
ok len=17624
Test #9:
score: 0
Accepted
time: 2071ms
memory: 440644kb
input:
128 abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a...
output:
abaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa bcbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb cdcccccccccccccccccccccccccccccccccccccc...
result:
ok len=16460
Test #10:
score: 0
Accepted
time: 2352ms
memory: 485560kb
input:
128 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc cccccccccccccccccccccccccccccccccccccccccc...
result:
ok len=16384
Test #11:
score: 0
Accepted
time: 3ms
memory: 23788kb
input:
10 AoenrfWTxhAiSipaV cJGloMoCBombqBsVuorNWL gqrmsIZGthdBIvNPWjTGgssBfbctzPCvCmMJWN MDYvQBZCaCmwSFnvQOmolkTmwWgysKuVmByj EOwjzBEgECXizqAZukRFAxdvrRhsGcIzQsFUMcXw mVNxPkaPPKUZEpswrhOqJerzhvfVwcNoDceNZPaskxTEhlGCMIoSqvAg JCPAAkYZoGOxpFNCj tsNvJHyeVCZqOHKzVsLoMnprENEmGSSxFGDDOafIIMVAbUtUIkAqmnrXUnWWfkAl...
output:
AcgMEmJtQnptFcoksenMLQXoWgmMEMuxBJYTcICgaVNaTfoyuAvDOAnedNDDPPPwIGaDOnjIlUvbJTVVQFLk HvApbVGYRBPuNjNkipYlWgO ScgzHNitvtRoLuUisITjuWCLGelWKqYoIAnAmIWTLOeMVHndqytXTd UBSuhtoimhfhdKivdyCqJxSbtnocRCEKicArQJKnRagqrJfNHY WqlPqHsSnpHcIfqCalIrqubIpBXqTVRBOYYQqRCQqJzyHRbbSCLzxsXOzNxSxSXcPhfHkNKClKWBJbg iLqfr...
result:
ok len=660
Test #12:
score: -100
Memory Limit Exceeded
input:
64 AQLPmEKRHtLKaVeVgUBkYfECFrvhbsXorapjINwkXhyCmkexRIVAZTsXaOihheHjstls AiIegrwbTMbBFdDQHGMgyOahunXRrySnKEmfKXQkpWdtNpGdgdBtPGfdcdnUvEqkfmvmSRzevtZkhPzjhDhTVLQCbaozNEXlqUgHeRshchY SFwbzOhRAEybYCGswuldoWkKloHghqiDybxtJPdzAWjmqxw mcRhokiMnxgAucSnasFcEXpZdEGEGzEGaEBAfGNEQAgQSTFKrMvxoUZTDKQMHksaciHoYXih...