QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#53954#74. Algorithm Teachingnot_so_organicTL 497ms114868kbC++206.7kb2022-10-06 13:38:292022-10-06 13:38:31

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:38:31]
  • 评测
  • 测评结果:TL
  • 用时:497ms
  • 内存:114868kb
  • [2022-10-06 13:38:29]
  • 提交

answer

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; 
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define MOD 1000000007
using ll = long long;
using dbl = long double;
//#define int ll

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<vii> vvii;
#define ff first
#define ss second
#define pb push_back
#define endl '\n'
#define all(s) s.begin(), s.end()
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
#define tc int t; cin>>t; while(t--)
#define fightFight cin.tie(0) -> sync_with_stdio(0)

// Have not tested MIS, but vertex-cover was tested so :)
struct DinicMatching {
    struct Edge {
        int to, rev;
        ll c, oc;
        int id;
        ll flow() { return max(oc - c, 0LL); } // if you need flows
        ll rflow() { return max(c - oc, 0LL); } // if you need reverse flows
    };

    int n, m;
    ll memoized_maxflow;
    bool match_called = false, maxflow_called = false, reachable_called = false;
    vi lvl, ptr, q, reachable, lmatch, rmatch;
    vector<vector<Edge>> adj;
    // Util functions, use from solve(). Passing true to xdex reverses transform
    int ldex(int v, bool rev = false) { return (!rev) ? v + 1 : v - 1; }
    int rdex(int v, bool rev = false) { return (!rev) ? n + v + 1 : v - n - 1; }
    bool isLeft(int v) { return (v >= 1 and v <= n); }
    bool isRight(int v) { return (v > n and v <= n+m); }

    void __addEdge(int a, int b, ll c, int id = 0, ll rcap = 0) {
        adj[a].push_back({b, sz(adj[b]), c, c, id});
        adj[b].push_back({a, sz(adj[a]) - 1, rcap, rcap, id});
    }
    // ENSURE that id is non-zero, necessary for reachable_dfs to work
    void addEdge(int l, int r, int id = 1){
        __addEdge(ldex(l), rdex(r), 1, id);
    }
    ll dfs(int v, int t, ll f) {
        if (v == t || !f) return f;
        for (int& i = ptr[v]; i < sz(adj[v]); i++) {
            Edge& e = adj[v][i];
            if (lvl[e.to] == lvl[v] + 1)
                if (ll p = dfs(e.to, t, min(f, e.c))) {
                    e.c -= p, adj[e.to][e.rev].c += p;
                    return p;
                }
        }
        return 0;
    }
    ll max_matching() {
        if(maxflow_called) return memoized_maxflow;
        maxflow_called = true;
        int s = 0, t = n + m + 1;
        ll flow = 0; q[0] = s;
        rep(L,0,31) do { // 'int L=30' maybe faster for random data
            lvl = ptr = vi(sz(q));
            int qi = 0, qe = lvl[s] = 1;
            while (qi < qe && !lvl[t]) {
                int v = q[qi++];
                for (Edge e : adj[v])
                    if (!lvl[e.to] && e.c >> (30 - L))
                        q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
            }
            while (ll p = dfs(s, t, LLONG_MAX)) flow += p;
        } while (lvl[t]);
        return memoized_maxflow = flow;
    }
    // Computes lmatch & rmatch. Access from solve().
    // Note: Can be made to store edge id also, just use vii instead.
    //       But if TL is generous, can get along with map<pii, int>.
    // COMMON MISTAKE: Storing {u, v} = {v, u} in map when u, v are 0 indexed for the set
    void match() {
        if(match_called) return;
        match_called = true;
        lmatch.assign(n, -1), rmatch.assign(m, -1);
        for(int u=0; u < n; u++){
            for(auto &e : adj[ldex(u)]){
                if(!e.id or e.flow() == 0) continue;
                int v = rdex(e.to, true);
                lmatch[u] = v;
                rmatch[v] = u;
            }
        }
    }
    void reachable_dfs(int v){
        if(reachable[v]) return;
        reachable[v] = true;
        for(auto &e : adj[v]){
            if(!e.id) continue;
            if(isLeft(v) and e.flow() == 0) reachable_dfs(e.to);
            if(isRight(v) and e.rflow() == 1) reachable_dfs(e.to);
        }
    }
    void solve_reachable(){
        if(reachable_called) return;
        reachable_called = true;
        max_matching(); match();
        reachable.assign(n + m + 2, 0);
        for(int v=0; v < n; v++)
            if(lmatch[v] == -1) reachable_dfs(ldex(v));
    }
    vi vertex_cover(){
        solve_reachable();
        vi vcover; vcover.reserve(memoized_maxflow);
        for(int v=0; v < n; v++)
            if(!reachable[ldex(v)]) vcover.pb(ldex(v));
        for(int v=0; v < m; v++)
            if(reachable[rdex(v)]) vcover.pb(rdex(v));
        return vcover;
    }
    vi maximum_independent_set(){
        solve_reachable();
        vi MIS; MIS.reserve(n + m - memoized_maxflow);
        for(int v=0; v < n; v++)
            if(reachable[ldex(v)]) MIS.pb(ldex(v));
        for(int v=0; v < m; v++)
            if(!reachable[rdex(v)]) MIS.pb(rdex(v));
        return MIS;
    }
    bool leftOfMinCut(int a) { return lvl[a] != 0; }

    DinicMatching(int N) : lvl(N), ptr(N), q(N), adj(N) {}
    DinicMatching(int _n, int _m) : DinicMatching(_n + _m + 2) {
        n = _n, m = _m;
        int source = 0, sink = n + m + 1;
        for(int v=0; v < n; v++) __addEdge(source, ldex(v), 1);
        for(int v=0; v < m; v++) __addEdge(rdex(v), sink, 1);
    }
};
void solve(){

    int n; cin >> n;
    int idx = 1;
    map<string, int> id;
    vector<vi> teachers;
    int max_nodes = 0;
    for(int i=0; i < n; i++){
        int a; cin >> a;
        vi t;
        for(int j=0; j < a; j++){
            string x; cin >> x;
            if(!id.count(x)) id[x] = idx++;
            t.pb(id[x]);
        }
        max_nodes += (1 << a);
        sort(all(t));
        teachers.pb(t);
    }

    auto get_submask = [&](vi &x, int mask){
        vi ret;
        for(int i=0; i < sz(x); i++)
            if(mask & (1 << i)) ret.pb(x[i]);
        return ret;
    };

    idx = 0;
    map<vi, int> subid;
    auto get_id = [&](vi &&x){
        if(subid.count(x)) return subid[x];
        else return subid[x] = idx++;
    };

    DinicMatching net(max_nodes, max_nodes);
    for(auto &t : teachers){
        for(int mask = 1; mask < (1 << sz(t)); mask++){
            int big_id = get_id(get_submask(t, mask));
            for(int i = mask; i > 0; i = (i-1) & mask){
                if(i == mask) continue;
                int small_id = get_id(get_submask(t, i));
                net.addEdge(big_id, small_id);
            }
        }
    }

    cout << idx - net.max_matching() << endl;

}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
    fightFight;
    solve();   
}

詳細信息

Test #1:

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

input:

1
3 DFS BFS DIJKSTRA

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 13ms
memory: 7916kb

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: 3800kb

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: 3ms
memory: 3952kb

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: 3ms
memory: 3876kb

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: 3ms
memory: 4028kb

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

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: 3872kb

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: 3932kb

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: 3768kb

input:

1
4 DFS MAXFLOW DP DIJKSTRA

output:

6

result:

ok single line: '6'

Test #11:

score: 0
Accepted
time: 15ms
memory: 7672kb

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: 3716kb

input:

2
4 BFS DFS LCA RMQ
2 PRIM KRUSKAL

output:

8

result:

ok single line: '8'

Test #13:

score: 0
Accepted
time: 40ms
memory: 12280kb

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: 497ms
memory: 114868kb

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: 305ms
memory: 52832kb

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: 388ms
memory: 62668kb

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: -100
Time Limit Exceeded

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:


result: