QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#759734#9558. The DevilIllusionaryDominanceML 2352ms485560kbC++205.0kb2024-11-18 11:36:412024-11-18 11:36:48

Judging History

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

  • [2024-11-18 11:36:48]
  • 评测
  • 测评结果:ML
  • 用时:2352ms
  • 内存:485560kb
  • [2024-11-18 11:36:41]
  • 提交

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...

output:


result: