QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#53963#74. Algorithm Teachingnot_so_organicAC ✓250ms26724kbC++202.9kb2022-10-06 13:43:022022-10-06 13:43:05

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-06 13:43:05]
  • 评测
  • 测评结果:AC
  • 用时:250ms
  • 内存:26724kb
  • [2022-10-06 13:43:02]
  • 提交

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;
  }
}

Details

Tip: Click on the bar to expand more detailed information

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'