QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#810265#74. Algorithm TeachingSGColinAC ✓106ms44864kbC++203.2kb2024-12-11 20:49:202024-12-11 20:49:21

Judging History

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

  • [2024-12-11 20:49:21]
  • 评测
  • 测评结果:AC
  • 用时:106ms
  • 内存:44864kb
  • [2024-12-11 20:49:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define fr            first
#define sc            second
#define pb            push_back
#define mp            make_pair
#define mt            make_tuple
#define pii           pair<int, int>
#define tiii          tuple<long, long, long>
#define all(s)        (s).begin(), (s).end()
#define lowbit(x)     ((x) & -(x))
#define rep(i, x, y)  for (int (i) = (x); (i) <= (y); ++(i))
#define per(i, x, y)  for (int (i) = (x); (i) >= (y); --(i))

inline bool getmin(int &a, int b) {return (a > b ? (a = b, true) : false);}
inline bool getmax(int &a, int b) {return (a < b ? (a = b, true) : false);}

const int N   = 110007;
const int inf = 1000000000;

namespace Hopcroft_Karp {

    bool vis[N];
    vector<int> e[N];
    int nl, nr, ml[N], mr[N], dl[N], dr[N]; // m for match, d for distance
    
    inline bool bfs() {
        static int q[N], hd, tl; hd = 1; tl = 0;
        memset(dl, -1, sizeof(int) * (nl + 1));
        memset(dr, -1, sizeof(int) * (nr + 1));
        for (int i = 1; i <= nl; ++i) if (!ml[i]) {dl[i] = 0; q[++tl] = i;}
        int dT = inf;
        while (hd <= tl) {
            int u = q[hd++];
            if (dl[u] >= dT) break;
            for (auto v : e[u])
                if (dr[v] == -1) {
                    dr[v] = dl[u] + 1;
                    if (!mr[v]) getmin(dT, dr[v] + 1);
                    else {dl[mr[v]] = dr[v] + 1; q[++tl] = mr[v];}
                }
        }
        return dT != inf;
    }

    bool dfs(int u) {
        for (auto v : e[u]) {
            if (vis[v] || dl[u] + 1 != dr[v]) continue;
            vis[v] = true;
            if (!mr[v] || dfs(mr[v])) {mr[v] = u; ml[u] = v; return true;}
        }
        return false;
    }

    inline void add(int u, int v) {e[u].push_back(v);}

    inline int max_matching() {
        int ans = 0;
        while(bfs()) {
            memset(vis, 0, sizeof(bool) * (nr + 1));
            for (int i = 1; i <= nl; ++i) if (!ml[i]) ans += dfs(i);
        }
        return ans;
    }
}

int tot, cnts;

bool vis[N];

unordered_map<string, int> tr;

map<vector<int>, int> id;

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) { 
        int k; cin >> k;
        vector<int> course(k);
        for (int j = 0; j < k; ++j) {
            string str;
            cin >> str;
            if (!tr[str]) tr[str] = ++cnts;
            course[j] = tr[str];
        }
        sort(all(course));
        vector<int> subset(1 << k);
        for (int S = 1; S < (1 << k); ++S) {
            vector<int> tmp(__builtin_popcount(S));
            for (int j = 0, tmpcnt = 0; j < k; ++j)
                if (S & (1 << j)) tmp[tmpcnt++] = course[j];
            if (!id[tmp]) id[tmp] = ++tot;
            subset[S] = id[tmp];
        }
        for (int S = 1; S < (1 << k); ++S) {
            int nwid = subset[S];
            if (vis[nwid]) continue;
            vis[nwid] = true;
            for (int s = (S & (S - 1)); s; s = (S & (s - 1))) Hopcroft_Karp::add(nwid, subset[s]);
        }  
    }
    Hopcroft_Karp::nl = Hopcroft_Karp::nr = tot;
    printf("%d\n", tot - Hopcroft_Karp::max_matching());
    return 0;
}  

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3700kb

input:

1
3 DFS BFS DIJKSTRA

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3856kb

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: 1ms
memory: 3820kb

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: 1ms
memory: 3816kb

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: 1ms
memory: 3772kb

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: 1ms
memory: 4036kb

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: 0ms
memory: 5816kb

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: 1ms
memory: 3884kb

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: 0ms
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: 0ms
memory: 3824kb

input:

1
4 DFS MAXFLOW DP DIJKSTRA

output:

6

result:

ok single line: '6'

Test #11:

score: 0
Accepted
time: 2ms
memory: 4108kb

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: 0ms
memory: 4088kb

input:

2
4 BFS DFS LCA RMQ
2 PRIM KRUSKAL

output:

8

result:

ok single line: '8'

Test #13:

score: 0
Accepted
time: 0ms
memory: 6204kb

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: 8ms
memory: 4236kb

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: 18ms
memory: 9504kb

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: 16ms
memory: 10384kb

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: 61ms
memory: 16384kb

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: 73ms
memory: 25324kb

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: 53ms
memory: 22028kb

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: 51ms
memory: 20336kb

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: 0ms
memory: 5956kb

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: 1ms
memory: 3752kb

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: 0ms
memory: 6028kb

input:

1
1 HAVEFUN

output:

1

result:

ok single line: '1'

Test #24:

score: 0
Accepted
time: 1ms
memory: 5792kb

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: 106ms
memory: 44864kb

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: 1ms
memory: 4036kb

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: 1ms
memory: 3792kb

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: 1ms
memory: 3796kb

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'