QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#53954 | #74. Algorithm Teaching | not_so_organic | TL | 497ms | 114868kb | C++20 | 6.7kb | 2022-10-06 13:38:29 | 2022-10-06 13:38:31 |
Judging History
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...