QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#53963 | #74. Algorithm Teaching | not_so_organic | AC ✓ | 250ms | 26724kb | C++20 | 2.9kb | 2022-10-06 13:43:02 | 2022-10-06 13:43:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
class HopcroftKarp {
vector<vector<int>> graph;
vector<int> dist, match;
vector<bool> used, visited;
void bfs() {
dist.assign(graph.size(), -1);
queue<int> q;
for (int i = 0; i < (int)graph.size(); i++) {
if (!used[i]) {
q.emplace(i);
dist[i] = 0;
}
}
while (!q.empty()) {
int a = q.front();
q.pop();
for (auto& b : graph[a]) {
int c = match[b];
if (c >= 0 && dist[c] == -1) {
dist[c] = dist[a] + 1;
q.emplace(c);
}
}
}
}
bool dfs(int a) {
visited[a] = true;
for (auto& b : graph[a]) {
int c = match[b];
if (c < 0 || (!visited[c] && dist[c] == dist[a] + 1 && dfs(c))) {
match[b] = a;
used[a] = true;
return true;
}
}
return false;
}
public:
HopcroftKarp(int n, int m) : graph(n), match(m, -1), used(n) {}
void add_edge(int u, int v) { graph[u].push_back(v); }
int node_count() const { return graph.size(); }
int max_bipartite_matching() {
int flow, ret = 0;
do {
bfs();
visited.assign(graph.size(), false);
flow = 0;
for (int i = 0; i < (int)graph.size(); i++) flow += !used[i] && dfs(i);
ret += flow;
} while (flow);
return ret;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
while (cin >> N) {
map<string, int> algo_idx;
map<vector<int>, int> node_idx;
vector<pair<int, int>> edges;
const auto get_node_idx = [&](const vector<int>& algo_idx_list) -> int {
if (!node_idx.count(algo_idx_list)) node_idx[algo_idx_list] = node_idx.size();
return node_idx[algo_idx_list];
};
for (int t = 0; t < N; t++) {
int A;
cin >> A;
vector<int> can_teach;
for (int i = 0; i < A; i++) {
string a;
cin >> a;
algo_idx.count(a) || algo_idx.emplace(a, algo_idx.size()).second;
can_teach.push_back(algo_idx[a]);
}
sort(can_teach.begin(), can_teach.end());
const int algo_n = can_teach.size();
for (int subset = 1; subset < (1 << algo_n); subset++) {
vector<int> algo_idx_list;
for (int j = 0; j < algo_n; j++)
if (subset & (1 << j)) algo_idx_list.push_back(can_teach[j]);
const int v = get_node_idx(algo_idx_list);
const int list_n = algo_idx_list.size();
for (int j = 0; j < list_n; j++) {
vector<int> algo_idx_list2 = algo_idx_list;
algo_idx_list2.erase(algo_idx_list2.begin() + j);
edges.emplace_back(get_node_idx(algo_idx_list2), v);
}
}
}
HopcroftKarp hk(node_idx.size(), node_idx.size());
for (const auto& [u, v] : edges) {
hk.add_edge(u, v);
}
cout << hk.node_count() - hk.max_bipartite_matching() << endl;
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3584kb
input:
1 3 DFS BFS DIJKSTRA
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3984kb
input:
100 3 BFS DFS DP 3 BFS DFS DIJKSTRA 3 BFS DFS MAXFLOW 3 BFS DFS GREEDY 3 BFS DFS LCA 3 BFS DP DIJKSTRA 3 BFS DP MAXFLOW 3 BFS DP GREEDY 3 BFS DP LCA 3 BFS DIJKSTRA MAXFLOW 3 BFS DIJKSTRA GREEDY 3 BFS DIJKSTRA LCA 3 BFS MAXFLOW GREEDY 3 BFS MAXFLOW LCA 3 BFS GREEDY LCA 3 DFS DP DIJKSTRA 3 DFS DP MAXF...
output:
35
result:
ok single line: '35'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3772kb
input:
16 1 BFS 1 DFS 1 DP 1 DIJKSTRA 1 MAXFLOW 1 GREEDY 4 BFS DIJKSTRA GREEDY DFS 3 DIJKSTRA GREEDY MAXFLOW 4 GREEDY DIJKSTRA DFS MAXFLOW 2 BFS DFS 3 GREEDY DFS BFS 4 MAXFLOW GREEDY DP DIJKSTRA 4 BFS DIJKSTRA MAXFLOW DP 2 GREEDY MAXFLOW 5 GREEDY DP MAXFLOW DFS BFS 6 MAXFLOW DFS GREEDY DP DIJKSTRA BFS
output:
20
result:
ok single line: '20'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
25 2 BFS DFS 2 BFS DP 2 BFS DIJKSTRA 2 BFS MAXFLOW 2 BFS GREEDY 2 DFS DP 2 DFS DIJKSTRA 2 DFS MAXFLOW 2 DFS GREEDY 2 DP DIJKSTRA 2 DP MAXFLOW 2 DP GREEDY 2 DIJKSTRA MAXFLOW 2 DIJKSTRA GREEDY 2 MAXFLOW GREEDY 5 DFS MAXFLOW GREEDY DP DIJKSTRA 2 DFS GREEDY 5 DIJKSTRA DFS MAXFLOW BFS DP 5 DP DFS DIJKSTR...
output:
20
result:
ok single line: '20'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3816kb
input:
30 3 BFS DFS DP 3 BFS DFS DIJKSTRA 3 BFS DFS MAXFLOW 3 BFS DFS GREEDY 3 BFS DP DIJKSTRA 3 BFS DP MAXFLOW 3 BFS DP GREEDY 3 BFS DIJKSTRA MAXFLOW 3 BFS DIJKSTRA GREEDY 3 BFS MAXFLOW GREEDY 3 DFS DP DIJKSTRA 3 DFS DP MAXFLOW 3 DFS DP GREEDY 3 DFS DIJKSTRA MAXFLOW 3 DFS DIJKSTRA GREEDY 3 DFS MAXFLOW GRE...
output:
20
result:
ok single line: '20'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
25 4 BFS DFS DP DIJKSTRA 4 BFS DFS DP MAXFLOW 4 BFS DFS DP GREEDY 4 BFS DFS DIJKSTRA MAXFLOW 4 BFS DFS DIJKSTRA GREEDY 4 BFS DFS MAXFLOW GREEDY 4 BFS DP DIJKSTRA MAXFLOW 4 BFS DP DIJKSTRA GREEDY 4 BFS DP MAXFLOW GREEDY 4 BFS DIJKSTRA MAXFLOW GREEDY 4 DFS DP DIJKSTRA MAXFLOW 4 DFS DP DIJKSTRA GREEDY ...
output:
20
result:
ok single line: '20'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3804kb
input:
16 5 BFS DFS DP DIJKSTRA MAXFLOW 5 BFS DFS DP DIJKSTRA GREEDY 5 BFS DFS DP MAXFLOW GREEDY 5 BFS DFS DIJKSTRA MAXFLOW GREEDY 5 BFS DP DIJKSTRA MAXFLOW GREEDY 5 DFS DP DIJKSTRA MAXFLOW GREEDY 3 BFS DIJKSTRA MAXFLOW 4 MAXFLOW DFS DP GREEDY 2 DIJKSTRA BFS 4 DIJKSTRA GREEDY MAXFLOW BFS 6 DIJKSTRA BFS DP ...
output:
20
result:
ok single line: '20'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3604kb
input:
11 6 BFS DFS DP DIJKSTRA MAXFLOW GREEDY 1 DFS 6 BFS DIJKSTRA MAXFLOW DFS GREEDY DP 2 BFS DP 2 GREEDY DP 5 GREEDY MAXFLOW DP BFS DIJKSTRA 2 DFS GREEDY 2 MAXFLOW GREEDY 5 DFS DP BFS MAXFLOW DIJKSTRA 2 GREEDY DIJKSTRA 3 BFS MAXFLOW DP
output:
20
result:
ok single line: '20'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3728kb
input:
87 3 BFS DFS DP 3 BFS DFS DIJKSTRA 3 BFS DFS MAXFLOW 3 BFS DFS GREEDY 3 BFS DFS LCA 3 BFS DFS RMQ 3 BFS DFS GEOMETRY 3 BFS DP DIJKSTRA 3 BFS DP MAXFLOW 3 BFS DP GREEDY 3 BFS DP LCA 3 BFS DP RMQ 3 BFS DP GEOMETRY 3 BFS DIJKSTRA MAXFLOW 3 BFS DIJKSTRA GREEDY 3 BFS DIJKSTRA LCA 3 BFS DIJKSTRA RMQ 3 BFS...
output:
84
result:
ok single line: '84'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
1 4 DFS MAXFLOW DP DIJKSTRA
output:
6
result:
ok single line: '6'
Test #11:
score: 0
Accepted
time: 4ms
memory: 3912kb
input:
2 10 MAXFLOW BFS DP DFS GEOMETRY GREEDY RMQ LCA UNIONFIND DIJKSTRA 2 MAXFLOW DIJKSTRA
output:
252
result:
ok single line: '252'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3676kb
input:
2 4 BFS DFS LCA RMQ 2 PRIM KRUSKAL
output:
8
result:
ok single line: '8'
Test #13:
score: 0
Accepted
time: 3ms
memory: 3956kb
input:
10 9 GEOMETRY DIJKSTRA DFS MAXFLOW GREEDY RMQ DP UNIONFIND LCA 10 RMQ DFS DP BFS LCA MAXFLOW UNIONFIND GREEDY GEOMETRY DIJKSTRA 3 BFS DP MAXFLOW 8 RMQ BFS GREEDY UNIONFIND MAXFLOW GEOMETRY DP LCA 9 BFS MAXFLOW DIJKSTRA GEOMETRY DFS LCA GREEDY UNIONFIND RMQ 7 BFS LCA GEOMETRY RMQ MAXFLOW UNIONFIND DF...
output:
252
result:
ok single line: '252'
Test #14:
score: 0
Accepted
time: 36ms
memory: 5064kb
input:
100 3 LCA BFS UNIONFIND 7 MAXFLOW DP RMQ DFS GEOMETRY LCA UNIONFIND 2 MAXFLOW UNIONFIND 9 GREEDY BFS UNIONFIND DIJKSTRA MAXFLOW LCA GEOMETRY DFS DP 3 DFS DP GEOMETRY 8 DP GEOMETRY DIJKSTRA RMQ BFS GREEDY DFS MAXFLOW 9 DIJKSTRA UNIONFIND DP GREEDY BFS DFS RMQ LCA GEOMETRY 8 LCA UNIONFIND DP DFS BFS R...
output:
252
result:
ok single line: '252'
Test #15:
score: 0
Accepted
time: 36ms
memory: 7200kb
input:
100 3 BQNKJPCAZI GHIDPTMSQK KTAQLPAKRK 2 MRWDUJEFEE JUJTAGRGSE 8 JAHPUIJYKH JFZCKMHFSV LLZQZWFTJJ WXCCNXDFUV ZKQNLPIDMY ATPTFBIVWL OLPMASMESX HXWMLFIEMA 7 EWZOANDAGA PDHYOTVCZB ZKDPOYYSSX ZOQMMIFLAZ DVPXQXYVDC SWJAVNZYCD HKGTIGYTGS 2 XRRBOMNOVS JMUWWORGUJ 3 ERUGELHBUJ SEPBQCUGJT SLKQIHPIQW 10 GDZNRS...
output:
4505
result:
ok single line: '4505'
Test #16:
score: 0
Accepted
time: 44ms
memory: 7472kb
input:
100 5 TVFEDEMLND RWAAAYHZRV IEVPVTXVLP LHQZKZJVHC JXYHNKBLKU 7 ILOWLRUWZD IJNUAGUKNR GDTCWTFRJN RJVSXORIOP NKCLIPSPMC AINLBPWNJR IYWXDXREVP 3 FJIDJFQBUH LQGKTYKPAY JYWROWHIKO 3 RMQ QDVHEXMUVT LNFHXRLEQL 6 ZPPVJFVSGH IQWZKGOTXK ZBHZOIATVX ECVWODTSWB JECLCKKKFS ZTTISJSJCG 5 LDCPDNQMMR RLHSHFKGCO ITOWL...
output:
4864
result:
ok single line: '4864'
Test #17:
score: 0
Accepted
time: 143ms
memory: 11220kb
input:
100 8 ILRAZVXODW GREEDY EPVLXJGRZP RMQ DFS UNIONFIND MCLZBHDTFP DP 9 LZCXQJMTDW DP TGTNLSIJOW ILRAZVXODW EPVLXJGRZP BFS GEOMETRY DFS MAXFLOW 9 FGRSZCKMJJ GREEDY TGTNLSIJOW FYACVCHOEU UNIONFIND MCLZBHDTFP BFS LZCXQJMTDW DFS 9 FYACVCHOEU BFS UNIONFIND IMPBXYLFQN PTDPYKQWER DFS DIJKSTRA ILRAZVXODW HQEN...
output:
8637
result:
ok single line: '8637'
Test #18:
score: 0
Accepted
time: 183ms
memory: 16352kb
input:
100 10 JRNCWUJJUB TIHDNDZUVF VGTXBOGHCG YBGWGLIODL PUOEKLAOVW RMLKDZSTHA DFS DP HAODTRSFZE ROMEHSVSUC 10 VQSIFEUVHQ HAODTRSFZE HAJSOIWMSH SHGRWYAAEC MAXFLOW BPPYFKGKQS BFS RMLKDZSTHA UNIONFIND KBVZEUYEAT 9 RMQ YLXSPBOBWQ OPATFVSFFN OYBAUNTRJB SHGRWYAAEC TTHIEQSUHE GGKCTURIFO SWGMQUWSEH BLAYSVLBJB 9 ...
output:
15421
result:
ok single line: '15421'
Test #19:
score: 0
Accepted
time: 127ms
memory: 14944kb
input:
100 8 NORWAYAWDR CLJAIJAONU OESBUOQEDB RYVYWVYBVL RDHCXVGKNK BLAXQSADIC KBLGTHKOGA GCEXUQWYNL 10 HYARPPABIS GECKYZTSEQ ZTZFIVMJHF ZJCVISLQED QFUKFNHPKL QKBHRDKVZU DPRCPAQTYZ IYYHORVGKG GYMGHTGLGN JVONHMCQRT 8 NUZGDTNALW CXVVKMJXVG NQHZHKSAQF IKGHEWCWDS IPOTTSGPYX JMUYVGWRCO JBZMXWMSCP IYJXBDPSHP 8 L...
output:
13272
result:
ok single line: '13272'
Test #20:
score: 0
Accepted
time: 114ms
memory: 14424kb
input:
100 9 DIJKSTRA VKCPWVXHJH FVKQAMUDFR BYBBQXWGBV XEGKKUNAXI VHPQQOPOWK UDCGWLWZWO ZLYPUPWEJL HBLBEIODQX 9 AAHOFGCSAX LCA KIPZGNXMOW TMHWUFCGOM GMASNCJJQA JTVQGKOLEZ KKNZTSHKUA ITCGHLVAZH VRMLEKYEXZ 9 FPEGQBCVKD TMHWUFCGOM SMEJHPVOEV LBEBTUDQFN DFS FRKBHBZIQF WMTEESYZNX AVWUJVVQYN JRUSHVGLGT 9 GWEKLAX...
output:
12600
result:
ok single line: '12600'
Test #21:
score: 0
Accepted
time: 3ms
memory: 3752kb
input:
88 4 BFS DFS DP DIJKSTRA 4 BFS DFS DP MAXFLOW 4 BFS DFS DP GREEDY 4 BFS DFS DP LCA 4 BFS DFS DP RMQ 4 BFS DFS DIJKSTRA MAXFLOW 4 BFS DFS DIJKSTRA GREEDY 4 BFS DFS DIJKSTRA LCA 4 BFS DFS DIJKSTRA RMQ 4 BFS DFS MAXFLOW GREEDY 4 BFS DFS MAXFLOW LCA 4 BFS DFS MAXFLOW RMQ 4 BFS DFS GREEDY LCA 4 BFS DFS G...
output:
102
result:
ok single line: '102'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
4 3 BFS DFS DIJKSTRA 4 BFS DFS LCA RMQ 3 DIJKSTRA BFS DFS 3 FLOYD DFS BFS
output:
10
result:
ok single line: '10'
Test #23:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
1 1 HAVEFUN
output:
1
result:
ok single line: '1'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3604kb
input:
3 4 FFEK DANTZIG DEMOUCRON FFT 4 PRIM KRUSKAL LCA FLOYD 4 DFS BFS DIJKSTRA RMQ
output:
18
result:
ok single line: '18'
Test #25:
score: 0
Accepted
time: 250ms
memory: 26724kb
input:
100 10 BFS DFS DP DIJKSTRA MAXFLOW GREEDY LCA RMQ GEOMETRY UNIONFIND 10 TCFFIUXZDV AHUFJJDVSC FJKBCAEMVF PVLARBOZVC EXHDCLKMMA WSCPKMLJDB TVBCIWMVZA BESVCCTNBP UMNOAJHYAS QDDDWKUCZB 10 UCAUJDWQTH UTXNRWWYQC NQSLCLXQFR OVLZBUWUTE TXNTDCWJEO ZVUXAAZWFM LJRPSDRUEY PDBNDMYAUT BCKPDQHDID XDBHGOYTAR 10 CT...
output:
25200
result:
ok single line: '25200'
Test #26:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
45 2 BFS DFS 2 BFS DP 2 BFS DIJKSTRA 2 BFS MAXFLOW 2 BFS GREEDY 2 BFS LCA 2 BFS RMQ 2 BFS GEOMETRY 2 BFS UNIONFIND 2 DFS DP 2 DFS DIJKSTRA 2 DFS MAXFLOW 2 DFS GREEDY 2 DFS LCA 2 DFS RMQ 2 DFS GEOMETRY 2 DFS UNIONFIND 2 DP DIJKSTRA 2 DP MAXFLOW 2 DP GREEDY 2 DP LCA 2 DP RMQ 2 DP GEOMETRY 2 DP UNIONFI...
output:
45
result:
ok single line: '45'
Test #27:
score: 0
Accepted
time: 3ms
memory: 3720kb
input:
70 4 BFS DFS DP DIJKSTRA 4 BFS DFS DP MAXFLOW 4 BFS DFS DP GREEDY 4 BFS DFS DP LCA 4 BFS DFS DP RMQ 4 BFS DFS DIJKSTRA MAXFLOW 4 BFS DFS DIJKSTRA GREEDY 4 BFS DFS DIJKSTRA LCA 4 BFS DFS DIJKSTRA RMQ 4 BFS DFS MAXFLOW GREEDY 4 BFS DFS MAXFLOW LCA 4 BFS DFS MAXFLOW RMQ 4 BFS DFS GREEDY LCA 4 BFS DFS G...
output:
70
result:
ok single line: '70'
Test #28:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
36 4 BFS DFS DP DIJKSTRA 4 BFS DFS DP MAXFLOW 4 BFS DFS DP GREEDY 4 BFS DFS DP LCA 4 BFS DFS DIJKSTRA MAXFLOW 4 BFS DFS DIJKSTRA GREEDY 4 BFS DFS DIJKSTRA LCA 4 BFS DFS MAXFLOW GREEDY 4 BFS DFS MAXFLOW LCA 4 BFS DFS GREEDY LCA 4 BFS DP DIJKSTRA MAXFLOW 4 BFS DP DIJKSTRA GREEDY 4 BFS DP DIJKSTRA LCA ...
output:
35
result:
ok single line: '35'