QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#626483 | #8759. 小班课 | gugg | TL | 10ms | 14208kb | C++20 | 4.9kb | 2024-10-10 09:33:10 | 2024-10-10 09:33:10 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <cmath>
#include <bitset>
#include <cassert>
#include <numeric>
using namespace std;
typedef long long ll;
const int inf = 1e9;
template<class T>
struct MaxFlow {
struct _Edge {
int to;
T cap;
_Edge(int to, T cap) : to(to), cap(cap) {}
};
int n;
std::vector<_Edge> e;
std::vector<std::vector<int>> g;
std::vector<int> cur, h;
MaxFlow() {}
MaxFlow(int n) {
init(n);
}
void init(int n) {
this->n = n;
e.clear();
g.assign(n, {});
cur.resize(n);
h.resize(n);
}
bool bfs(int s, int t) {
h.assign(n, -1);
std::queue<int> que;
h[s] = 0;
que.push(s);
while (!que.empty()) {
const int u = que.front();
que.pop();
for (int i : g[u]) {
auto [v, c] = e[i];
if (c > 0 && h[v] == -1) {
h[v] = h[u] + 1;
if (v == t) {
return true;
}
que.push(v);
}
}
}
return false;
}
T dfs(int u, int t, T f) {
if (u == t) {
return f;
}
auto r = f;
for (int &i = cur[u]; i < int(g[u].size()); ++i) {
const int j = g[u][i];
auto [v, c] = e[j];
if (c > 0 && h[v] == h[u] + 1) {
auto a = dfs(v, t, std::min(r, c));
e[j].cap -= a;
e[j ^ 1].cap += a;
r -= a;
if (r == 0) {
return f;
}
}
}
return f - r;
}
void addEdge(int u, int v, T c) {
g[u].push_back(e.size());
e.emplace_back(v, c);
g[v].push_back(e.size());
e.emplace_back(u, 0);
}
T flow(int s, int t) {
T ans = 0;
while (bfs(s, t)) {
cur.assign(n, 0);
ans += dfs(s, t, std::numeric_limits<T>::max());
}
return ans;
}
std::vector<bool> minCut() {
std::vector<bool> c(n);
for (int i = 0; i < n; i++) {
c[i] = (h[i] != -1);
}
return c;
}
struct Edge {
int from;
int to;
T cap;
T flow;
};
std::vector<Edge> edges() {
std::vector<Edge> a;
for (int i = 0; i < e.size(); i += 2) {
Edge x;
x.from = e[i + 1].to;
x.to = e[i].to;
x.cap = e[i].cap + e[i + 1].cap;
x.flow = e[i + 1].cap;
a.push_back(x);
}
return a;
}
};
void solve()
{
int n, m;
cin >> n >> m;
int b[m + 10];
for (int i = 1; i <= m; i ++) cin >> b[i];
MaxFlow<int> flow(n + m + 3);
for (int i = 1; i <= n; i ++)
flow.addEdge(n + m + 1, i, 1);
for (int i = 1; i <= m; i ++)
flow.addEdge(n + i, n + m + 2, b[i]);
vector<int> a[n + 10];
for (int i = 1; i <= n; i ++)
{
int k;
cin >> k;
while (k --)
{
int x;
cin >> x;
a[i].push_back(x);
flow.addEdge(i, n + x, 1);
}
}
int ans = flow.flow(n + m + 1, n + m + 2);
cout << ans << '\n';
int match[n + 10] = {0};
bool st[n + 10] = {0};
bool used[m + 10] = {0};
for (int i = 1; i <= m; i ++)
if (!b[i]) used[i] = true;
auto e = flow.e;
for (int i = 0; i < e.size(); i += 2)
{
if (!e[i].cap && e[i + 1].to <= n)
{
int u = e[i + 1].to, v = e[i].to - n;
match[u] = v;
}
}
set<int> del;
int cnt = 0;
vector<int> p;
while (cnt < ans)
{
for (int i = 1; i <= n; i ++)
{
if (st[i]) continue;
int fir = -1;
for (int x : a[i])
if (!used[x])
{
fir = x;
break;
}
if (fir == match[i])
{
p.push_back(i);
st[i] = true;
b[fir] --;
if (!b[fir]) used[fir] = true;
cnt ++;
break;
}
}
}
for (auto x : p) cout << x << ' ';
for (int i = 1; i <= n; i ++)
if (!st[i]) cout << i << ' ';
cout << '\n';
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tt = 1;
cin >> tt;
while (tt --)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3824kb
input:
3 5 5 1 1 1 1 1 4 1 3 2 4 1 5 4 3 4 2 1 2 3 5 1 1 5 3 1 2 2 2 1 2 2 1 2 2 1 3 2 1 3 2 1 3 5 5 1 1 1 1 1 2 1 2 2 5 4 2 3 2 2 4 3 2 5 1
output:
5 2 4 3 5 1 5 5 1 2 3 4 5 2 3 4 5 1
result:
ok Correct!
Test #2:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
250 2 1 2 1 1 1 1 1 1 1 0 2 2 1 1 1 1 2 2 1 2 2 0 2 2 1 2 1 2 1 1 1 1 1 1 2 1 0 0 1 2 1 0 0 2 1 2 1 1 0 1 2 1 0 0 2 1 2 1 1 1 1 1 1 1 1 1 1 2 1 0 1 2 2 2 2 0 1 1 1 2 1 1 1 0 1 1 1 0 1 2 0 1 1 1 2 2 1 1 1 1 2 1 2 2 2 1 1 2 2 1 2 2 1 1 2 0 1 1 2 2 1 2 1 1 0 2 2 2 0 1 1 1 2 1 1 1 1 1 2 1 2 0 1 1 1 1 1 ...
output:
2 1 2 0 1 2 1 2 2 1 2 1 1 0 1 0 1 1 1 2 0 1 2 1 2 1 1 0 1 1 1 2 0 1 0 1 0 1 2 1 2 2 1 2 1 1 1 1 2 1 1 2 1 1 1 2 1 1 1 1 2 1 0 1 2 1 1 1 1 0 1 1 1 2 1 2 0 1 0 1 1 1 2 2 1 2 0 1 0 1 0 1 0 1 2 2 1 2 1 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 2 1 2 2 1 2 1 2 1 1 1...
result:
ok Correct!
Test #3:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
166 3 3 1 1 1 0 2 2 3 0 3 3 0 3 0 0 2 1 3 0 3 3 0 0 3 0 2 2 3 0 3 3 2 0 1 2 2 3 0 2 3 2 3 3 0 2 1 2 3 1 0 2 2 1 3 3 1 1 1 2 3 1 2 1 2 1 3 3 3 2 1 0 1 3 0 0 3 3 1 1 1 1 2 0 2 2 3 3 3 1 1 1 0 1 2 2 2 1 3 3 0 0 3 1 1 2 1 3 1 3 3 3 0 1 2 2 2 3 2 2 3 0 3 3 2 0 1 0 1 1 0 3 3 1 2 0 2 2 1 1 1 0 3 3 1 0 2 0 ...
output:
1 2 1 3 0 1 2 3 1 2 1 3 1 1 2 3 2 1 3 2 3 3 1 2 0 1 2 3 2 1 3 2 2 2 3 1 2 2 3 1 2 1 2 3 1 2 1 3 2 1 2 3 1 3 1 2 1 3 1 2 2 1 2 3 2 2 3 1 0 1 2 3 2 2 3 1 0 1 2 3 1 1 2 3 2 1 2 3 1 2 1 3 3 1 2 3 3 1 2 3 0 1 2 3 1 1 2 3 2 1 2 3 2 1 2 3 2 1 3 2 2 1 3 2 1 1 2 3 2 2 3 1 1 1...
result:
ok Correct!
Test #4:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
125 4 4 3 1 0 0 1 2 0 2 1 3 3 2 3 1 4 4 2 0 1 1 2 1 3 2 1 2 2 4 1 0 4 4 2 0 1 1 2 2 3 3 3 2 4 1 2 0 4 4 0 1 1 2 2 3 1 1 4 3 1 2 4 0 4 4 1 1 1 1 2 3 2 2 4 2 0 2 4 2 4 4 2 2 0 0 3 2 1 4 2 3 4 1 2 1 3 4 4 2 0 0 2 1 2 3 3 2 1 2 3 2 2 2 1 4 4 1 2 0 1 1 4 0 0 0 4 4 3 0 0 1 3 2 1 3 0 2 1 4 2 4 3 4 4 1 2 1 ...
output:
3 1 3 4 2 3 1 2 3 4 2 1 2 3 4 3 1 2 3 4 3 1 2 4 3 2 1 3 2 4 2 2 4 1 3 1 1 2 3 4 3 1 3 4 2 3 2 3 1 4 0 1 2 3 4 2 1 2 3 4 2 1 4 2 3 2 2 3 1 4 4 2 3 4 1 2 1 3 2 4 2 2 3 1 4 2 1 2 3 4 3 1 2 3 4 4 1 2 3 4 3 1 2 4 3 1 1 2 3 4 2 2 3 1 4 3 1 2 3 4 2 2 4 1 3 4 1 2 3 4 2 1 4 2 3 3 1...
result:
ok Correct!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
100 5 5 2 1 2 0 0 0 2 3 2 3 5 4 3 2 1 2 0 5 5 0 2 0 0 3 1 5 0 1 1 0 0 5 5 0 1 3 0 1 2 5 4 2 1 5 0 0 3 3 1 4 5 5 1 1 0 2 1 1 2 0 2 4 5 0 1 4 5 5 0 1 1 2 1 2 4 2 0 2 1 3 0 1 1 5 5 0 0 2 2 1 2 4 3 1 4 0 3 5 4 1 3 5 1 2 5 5 1 2 1 0 1 2 1 2 0 3 3 5 2 2 4 3 0 5 5 1 0 1 1 2 0 1 4 1 3 1 3 0 5 5 1 2 1 1 0 1 ...
output:
3 2 3 4 1 5 1 1 2 3 4 5 2 1 5 2 3 4 3 1 3 5 2 4 2 1 3 2 4 5 4 2 5 4 1 3 3 1 4 3 2 5 2 2 3 1 4 5 1 1 2 3 4 5 4 1 2 3 4 5 2 2 3 1 4 5 2 1 4 2 3 5 3 2 3 5 1 4 3 3 4 1 2 5 3 1 2 4 3 5 3 1 3 2 4 5 2 1 3 2 4 5 3 1 4 5 2 3 1 1 2 3 4 5 3 2 3 5 1 4 1 2 1 3 4 5 2 2 3 1 4 5 2 1 4 2 3 5 2...
result:
ok Correct!
Test #6:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
10 45 47 3 0 2 0 1 1 1 0 2 0 1 0 0 3 0 0 0 4 0 1 0 0 1 2 1 1 1 0 1 1 1 0 0 0 0 1 0 0 0 1 2 4 1 2 1 2 3 7 1 37 21 3 13 43 22 0 10 23 46 22 40 12 19 47 27 16 42 4 29 19 45 35 10 6 26 2 43 41 7 9 16 42 44 5 39 40 34 46 14 3 34 3 38 8 10 5 38 23 19 37 9 34 0 5 31 29 15 13 35 3 40 4 28 1 7 6 29 12 9 35 2...
output:
33 1 3 7 11 6 12 14 15 16 17 19 21 25 29 5 30 31 36 37 10 4 13 18 24 34 35 38 39 8 40 42 43 44 2 9 20 22 23 26 27 28 32 33 41 45 39 3 7 10 11 12 14 15 16 17 18 19 20 24 29 30 32 33 35 36 40 21 26 6 23 25 28 5 1 31 34 38 39 41 42 9 43 44 2 45 4 8 13 22 27 37 36 1 3 4 6 8 10 11 16 17 20 21 18 23 2 2...
result:
ok Correct!
Test #7:
score: 0
Accepted
time: 2ms
memory: 3896kb
input:
1 499 497 1 2 0 2 0 1 0 0 0 2 1 2 0 3 1 2 0 0 0 1 0 1 0 2 1 0 1 0 1 1 1 2 0 1 0 1 0 2 2 3 1 1 2 1 0 0 1 0 2 3 0 1 0 0 2 0 1 2 1 0 0 1 2 0 0 2 0 2 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 1 2 3 0 0 0 4 2 2 1 2 2 0 1 0 1 0 2 0 1 0 2 0 0 1 1 1 3 2 0 2 2 2 0 1 1 1 1 1 0 1 0 1 1 1 1 1 2 0 0 1 0 2 1 2 1 2 1 0 1 ...
output:
482 1 2 3 4 5 6 7 9 10 12 13 14 16 17 18 19 22 24 25 27 28 29 30 31 32 33 34 35 36 38 40 41 42 43 44 45 46 47 48 49 50 51 53 54 55 56 57 58 59 60 61 63 64 66 68 70 71 72 73 74 75 76 77 78 80 81 82 83 84 86 87 88 89 90 91 92 93 95 96 97 98 100 101 102 104 105 106 107 110 111 112 113 114 115 117 118 1...
result:
ok Correct!
Test #8:
score: 0
Accepted
time: 10ms
memory: 14208kb
input:
1 498 499 0 1 1 0 1 0 1 0 0 0 0 2 0 3 1 2 4 0 1 0 1 1 0 0 0 1 1 0 0 2 2 0 1 1 1 0 4 1 1 2 1 0 0 1 2 0 1 2 1 0 1 2 0 2 1 2 2 0 2 2 0 1 0 2 0 0 3 0 1 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 2 1 1 0 1 0 1 0 0 0 1 1 2 0 1 0 2 1 1 2 2 0 0 0 0 2 0 2 1 0 1 0 2 0 1 3 1 1 1 0 1 3 0 1 0 1 0 0 1 3 2 3 2 1 1 0 2 ...
output:
498 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok Correct!
Test #9:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
5 99 96 2 0 0 1 1 2 1 0 1 1 1 0 0 0 1 0 1 1 2 1 1 1 1 1 0 1 2 4 0 0 0 2 2 1 1 1 1 1 0 2 0 0 0 1 1 3 0 1 0 0 1 2 1 4 1 2 1 0 1 0 0 2 0 0 0 2 3 2 1 0 1 2 2 0 1 1 0 0 1 0 0 1 2 1 3 1 3 1 3 0 3 0 0 2 2 2 2 14 58 1 55 2 53 69 0 0 1 76 2 23 38 1 41 2 74 54 0 0 2 83 91 0 0 0 1 48 0 0 1 96 2 76 52 1 17 2 51...
output:
48 2 3 6 7 9 12 16 19 20 21 22 24 25 26 30 34 23 35 38 39 40 44 45 46 47 52 53 56 57 60 62 65 67 69 71 72 73 74 78 82 83 84 59 87 88 42 92 99 1 4 5 8 10 11 13 14 15 17 18 27 28 29 31 32 33 36 37 41 43 48 49 50 51 54 55 58 61 63 64 66 68 70 75 76 77 79 80 81 85 86 89 90 91 93 94 95 96 97 98 44 7 8 1...
result:
ok Correct!
Test #10:
score: 0
Accepted
time: 1ms
memory: 3908kb
input:
5 99 97 0 2 4 0 0 2 0 1 1 1 0 1 0 3 0 1 1 1 1 0 0 1 0 0 1 2 0 0 1 3 1 2 0 2 1 1 1 3 3 1 2 1 0 1 0 1 0 2 0 0 0 0 1 2 3 1 1 1 0 1 0 1 0 0 1 2 1 2 1 1 1 2 2 3 1 1 0 0 1 1 0 0 1 1 2 1 2 2 0 1 1 1 2 0 1 3 1 2 56 63 2 52 45 4 26 56 80 10 2 27 19 1 81 2 38 64 1 83 1 8 3 14 81 60 3 63 28 15 5 59 33 80 88 56...
output:
72 1 3 4 6 7 8 9 11 12 13 14 16 17 20 22 23 24 25 26 28 29 30 32 33 34 35 36 37 39 40 41 42 44 45 46 47 48 49 50 53 54 57 58 59 60 62 18 63 64 65 66 68 71 72 73 55 76 77 78 79 82 83 27 52 85 90 91 94 95 96 98 99 2 5 10 15 19 21 31 38 43 51 56 61 67 69 70 74 75 80 81 84 86 87 88 89 92 93 97 67 2 7 8...
result:
ok Correct!
Test #11:
score: -100
Time Limit Exceeded
input:
5 99 98 4 0 1 1 3 2 0 1 4 0 1 1 2 2 1 2 0 0 1 2 1 2 0 1 1 1 2 0 2 0 0 3 0 2 0 0 1 1 1 0 1 1 1 2 0 1 1 0 1 1 1 0 0 1 0 0 2 1 2 3 3 0 0 0 0 0 1 2 1 1 0 3 0 0 0 1 2 0 0 0 0 1 0 2 2 1 2 1 0 1 0 0 1 1 2 3 3 0 5 72 78 90 7 60 6 69 37 10 41 4 59 10 61 85 79 5 7 58 3 55 1 50 6 59 24 30 26 77 21 2 29 21 10 7...