QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#915 | #295930 | #7777. Intro: Dawn of a New Era | nodgd | willow | Failed. | 2024-09-26 21:07:57 | 2024-09-26 21:07:57 |
详细
Extra Test:
Accepted
time: 1801ms
memory: 65328kb
input:
100000 2 5133 4551 2 8873 13905 2 16895 9092 2 18036 17939 2 10385 8455 2 10515 10242 2 5343 9491 2 18212 16191 2 14481 15198 2 19076 19423 2 14971 15987 2 5692 8273 2 14403 16840 2 17730 14989 2 3666 1229 2 9085 8082 2 2191 6310 2 9287 9727 2 9802 5161 2 2412 3966 2 15900 10882 2 15790 13806 2 9155...
output:
99054 235 96311 30659 64293 70993 85014 54486 82248 73815 33897 27791 94325 18260 23533 51862 78039 63382 11036 14538 21884 16596 51361 44724 9186 18117 62085 63712 65760 84773 5392 49998 84725 91295 84226 75289 92859 28211 20480 44643 76565 31716 36105 37911 38525 49491 84043 85454 6831 7950 17503 ...
result:
ok correct!
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#295930 | #7777. Intro: Dawn of a New Era | willow | AC ✓ | 507ms | 83804kb | C++14 | 5.7kb | 2024-01-01 16:30:29 | 2024-10-13 20:50:44 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 300005;
const int MAXM = 1000005;
const int INF = 0x3f3f3f3f;
template <typename T> inline void read(T &WOW) {
T x = 0, flag = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') flag = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
WOW = flag * x;
}
struct BoundFlow {
int n, S, T, in[MAXN], SS, TT;
int level[MAXN], q[MAXN], head, tail;
struct Edge {
int v, w, nxt;
} e[MAXM << 1];
int eCnt, first[MAXN], used[MAXN];
inline void AddEdge(int u, int v, int w) {
e[++eCnt].v = v;
e[eCnt].w = w;
e[eCnt].nxt = first[u];
first[u] = eCnt;
}
inline void Add(int u, int v, int w) {
AddEdge(u, v, w);
AddEdge(v, u, 0);
}
inline void Add2(int u, int v, int l, int r) {
in[v] += l;
in[u] -= l;
Add(u, v, r - l);
}
void Init(int _n) {
SS = _n + 1;
n = TT = _n + 2;
for (int i = 1; i <= n; ++i) {
first[i] = 0;
}
eCnt = 1;
}
bool BFS() {
for (int i = 1; i <= n; ++i) {
level[i] = -1;
used[i] = first[i];
}
level[S] = 0;
q[head = tail = 1] = S;
while (head <= tail) {
int u = q[head++];
if (u == T) return 1;
for (int i = first[u]; i; i = e[i].nxt) {
int v = e[i].v;
if (e[i].w && level[v] == -1) {
level[v] = level[u] + 1;
q[++tail] = v;
}
}
}
return 0;
}
int DFS(int u, int flow) {
if (u == T) return flow;
int ret = 0;
for (int i = used[u]; i; i = e[i].nxt, used[u] = i) {
int v = e[i].v;
if (e[i].w && level[v] == level[u] + 1) {
int tmp = DFS(v, min(flow, e[i].w));
e[i].w -= tmp;
e[i ^ 1].w += tmp;
flow -= tmp;
ret += tmp;
if (!flow) break;
}
}
if (!ret) level[u] = -1;
return ret;
}
int Dinic(int s, int t) {
S = s; T = t;
int ret = 0;
while (BFS()) {
ret += DFS(S, INF);
}
return ret;
}
int MinBoundFlow(int s, int t) {
int sum = 0;
for (int i = 1; i <= n; ++i) {
if (in[i] > 0) {
Add(SS, i, in[i]);
sum += in[i];
} else if (in[i] < 0) {
Add(i, TT, -in[i]);
}
}
int tmp = Dinic(SS, TT);
Add(t, s, INF);
tmp += Dinic(SS, TT);
assert(tmp == sum);
return e[eCnt].w;
}
} F;
int n, m, w[MAXN], mx[MAXN];
vector<int> c[MAXN];
int S, T, ID, id1[MAXN], id2[MAXN];
int type[MAXM << 1], fr[MAXM << 1], to[MAXM << 1], pre[MAXN], nxt[MAXN], on[MAXN];
vector<int> g1[MAXN], g2[MAXN], single[MAXN];
void solve() {
read(n);
for (int i = 1; i <= n; ++i) {
int k; read(k);
c[i].resize(k);
for (int j = 0; j < k; ++j) {
read(c[i][j]);
}
sort(c[i].begin(), c[i].end());
w[++m] = c[i][k - 1];
}
sort(w + 1, w + m + 1);
m = unique(w + 1, w + m + 1) - (w + 1);
ID = n;
for (int i = 1; i <= m; ++i) {
id1[i] = ++ID;
id2[i] = ++ID;
}
S = ++ID; T = ++ID;
F.Init(T);
for (int i = 1; i <= n; ++i) {
F.Add2(S, i, 0, INF);
}
for (int i = 1; i <= m; ++i) {
F.Add2(id1[i], id2[i], 1, INF);
F.Add2(id2[i], T, 0, INF);
}
int L = F.eCnt;
for (int i = 1; i <= n; ++i) {
int k = c[i].size();
for (int j = 0; j < k - 1; ++j) {
int pos = lower_bound(w + 1, w + m + 1, c[i][j]) - w;
if (w[pos] != c[i][j]) continue;
F.Add2(id2[pos], i, 0, 1);
int e = F.eCnt;
type[e] = 1; fr[e] = pos; to[e] = i;
}
mx[i] = lower_bound(w + 1, w + m + 1, c[i][k - 1]) - w;
F.Add2(i, id1[mx[i]], 0, 1);
int e = F.eCnt;
type[e] = 2; fr[e] = i; to[e] = mx[i];
}
int R = F.eCnt;
printf("%d\n", n - F.MinBoundFlow(S, T));
for (int i = L + 2; i <= R; i += 2) {
if (F.e[i].w) {
if (type[i] == 1) {
g1[fr[i]].push_back(to[i]);
} else {
g2[to[i]].push_back(fr[i]);
}
}
}
for (int i = 1; i <= m; ++i) {
int k = min(g1[i].size(), g2[i].size());
for (int j = 0; j < k; ++j) {
pre[g1[i][j]] = g2[i][j];
nxt[g2[i][j]] = g1[i][j];
on[g1[i][j]] = on[g2[i][j]] = 1;
}
}
for (int i = 1; i <= n; ++i) {
if (!on[i]) {
single[mx[i]].push_back(i);
}
}
for (int i = 1; i <= n; ++i) {
if (pre[i] || !nxt[i]) continue;
for (int u = i; u; u = nxt[u]) {
printf("%d ", u);
if (single[mx[u]].size()) {
for (auto x : single[mx[u]]) {
printf("%d ", x);
}
single[mx[u]].clear();
}
}
}
for (int i = 1; i <= m; ++i) {
if (single[i].size()) {
for (auto x : single[i]) {
printf("%d ", x);
}
}
}
printf("\n");
}
int main() {
solve();
return 0;
}