QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#606457 | #6308. Magic | nhuang685 | WA | 21ms | 5456kb | C++23 | 7.0kb | 2024-10-03 08:53:47 | 2024-10-03 08:53:47 |
Judging History
answer
/**
* @author n685
* @brief
* @date 2024-10-02 17:47:12
*
*
*/
#include <utility>
#include "bits/stdc++.h"
#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif
namespace rs = std::ranges;
namespace rv = std::views;
struct Node {
std::array<int, 2> ch{-1, -1};
};
struct Seg {
int sz{};
std::vector<Node> data;
std::vector<int> rts;
Seg() = default;
explicit Seg(int sz_, int nrts)
: sz{static_cast<int>(std::bit_ceil<uint32_t>(sz_))},
rts(nrts, -1) {}
int copy_node(int ind) {
if (ind == -1) {
data.emplace_back();
} else {
data.push_back(data[ind]);
}
return static_cast<int>(data.size()) - 1;
}
void nch(int node, int ch) {
int ind = copy_node(data[node].ch[ch]);
data[node].ch[ch] = ind;
}
void upd(int i, int node, int l, int r) {
if (l == r) {
return;
}
int mid = (l + r) / 2;
if (i <= mid) {
nch(node, 0);
upd(i, data[node].ch[0], l, mid);
} else {
nch(node, 1);
upd(i, data[node].ch[1], mid + 1, r);
}
}
void upd(int t, int i) { upd(i, rts[t], 0, sz - 1); }
bool is_there(int i, int node, int l, int r) {
if (l == r) {
return true;
}
int mid = (l + r) / 2;
if (i <= mid) {
if (data[node].ch[0] == -1) {
return false;
}
return is_there(i, data[node].ch[0], l, mid);
}
if (data[node].ch[1] == -1) {
return false;
}
return is_there(i, data[node].ch[1], mid + 1, r);
}
bool is_there(int t, int i) { return is_there(i, rts[t], 0, sz - 1); }
void new_rt(int ind) { rts[ind] = copy_node(-1); }
void copy_rt(int rc, int ind) { rts[rc] = copy_node(rts[ind]); }
#ifdef LOCAL
void debug(std::vector<int> &s, int ll, int rr, int node, int l, int r) {
if (l == r) {
s.push_back(l);
}
int mid = (l + r) / 2;
if (data[node].ch[0] != -1 && ll <= mid) {
debug(s, ll, rr, data[node].ch[0], l, mid);
}
if (data[node].ch[1] != -1 && rr > mid) {
debug(s, ll, rr, data[node].ch[1], mid + 1, r);
}
}
std::vector<int> debug(int t, int ll, int rr) {
std::vector<int> ans;
debug(ans, ll, rr, rts[t], 0, sz - 1);
return ans;
}
#else
std::string debug(int t) { return ""; }
#endif
};
struct II {
int l, r;
};
struct Flow {
int sz, s = -1, t = -1;
std::vector<bool> vis;
Seg &adj;
std::vector<II> ⅈ
std::vector<int> left;
std::vector<bool> is_left;
explicit Flow(
int _sz,
Seg &adj_,
std::vector<II> &ii_,
std::vector<int> left_
)
: sz(_sz),
vis(sz),
adj(adj_),
ii(ii_),
left(std::move(left_)),
is_left(sz) {
for (int i : left) {
is_left[i] = true;
}
}
std::vector<int> l, h;
void bfs() {
l.assign(sz, static_cast<int>(1e9));
l[s] = 0;
std::queue<int> q;
q.push(s);
while (!q.empty()) {
int node = q.front();
q.pop();
if (node == s) {
for (int i : left) {
if (!vis[i] && l[i] > l[node] + 1) {
l[i] = l[node] + 1;
q.push(i);
}
}
} else if (is_left[node]) {
for (int i = ii[node].l; i < ii[node].r; ++i) {
if (adj.is_there(node, i) && l[i] > l[node] + 1) {
l[i] = l[node] + 1;
q.push(i);
}
}
} else if (node != t) {
if (!vis[node] && l[t] > l[node] + 1) {
l[t] = l[node] + 1;
}
for (int i = ii[node].l; i < ii[node].r; ++i) {
if (adj.is_there(node, i) && l[i] > l[node] + 1) {
l[i] = l[node] + 1;
q.push(i);
}
}
}
// for (Edge &e : adj[node]) {
// if (e.cap > 0 && l[e.v] > l[node] + 1) {
// l[e.v] = l[node] + 1;
// q.push(e.v);
// }
// }
}
}
int dfs(int node) {
if (node == t) {
return 1;
}
if (node == s) {
for (; h[node] < static_cast<int>(left.size()); ++h[node]) {
int i = left[h[node]];
if (!vis[i] && l[i] == l[node] + 1) {
int val = dfs(i);
if (val > 0) {
vis[i] = true;
return 1;
}
}
}
} else if (is_left[node]) {
if (h[node] == 0) {
h[node] = ii[node].l;
}
for (; h[node] < ii[node].r; ++h[node]) {
int i = h[node];
if (adj.is_there(node, i) && l[i] == l[node] + 1) {
int val = dfs(i);
if (val > 0) {
vis[i] = true;
return 1;
}
}
}
} else {
if (!vis[node] && l[t] == l[node] + 1) {
vis[node] = true;
return 1;
}
if (h[node] == 0) {
h[node] = ii[node].l;
}
for (; h[node] < ii[node].r; ++h[node]) {
int i = h[node];
if (vis[i] && adj.is_there(node, i) && l[i] == l[node] + 1) {
int val = dfs(i);
if (val > 0) {
return 1;
}
}
}
}
// for (; h[node] < static_cast<int>(adj[node].size()); ++h[node]) {
// Edge &e = adj[node][h[node]];
// if (e.cap > 0 && l[e.v] == l[node] + 1) {
// T val = dfs(e.v, std::min(f, e.cap));
// if (val) {
// e.cap -= val;
// adj[e.v][e.rev].cap += val;
// return val;
// }
// }
// }
return 0;
}
int max_flow(int _s, int _t) {
s = _s;
t = _t;
bfs();
int ans = 0;
while (l[t] != static_cast<int>(1e9)) {
h.assign(sz, 0);
// ans += dfs(s, std::numeric_limits<T>::max());
while (int res = dfs(s)) {
ans += res;
}
bfs();
}
return ans;
}
};
int main() {
#ifndef LOCAL
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#endif
start_clock();
int n;
std::cin >> n;
std::vector<II> ii(n);
std::vector<II> both(2 * n);
std::vector<int> left;
for (auto &[l, r] : ii) {
std::cin >> l >> r;
--l;
--r;
left.push_back(l);
}
rs::sort(ii, {}, &II::l);
for (int i = 0; i < n; ++i) {
both[ii[i].l] = ii[i];
both[ii[i].r] = ii[i];
}
Seg adj(2 * n, 2 * n);
for (int i = 0; i < n; ++i) {
if (i == 0) {
adj.new_rt(ii[i].l);
} else {
adj.copy_rt(ii[i].l, ii[i - 1].l);
}
if (i > 0) {
adj.upd(ii[i].l, ii[i - 1].r);
}
}
rs::sort(ii, {}, &II::r);
for (int i = n - 1; i >= 0; --i) {
if (i == n - 1) {
adj.new_rt(ii[i].r);
} else {
adj.copy_rt(ii[i].r, ii[i + 1].r);
}
if (i < n - 1) {
adj.upd(ii[i].r, ii[i + 1].l);
}
}
const int s = 2 * n, t = 2 * n + 1;
Flow flow(2 * n + 2, adj, both, left);
std::cout << 2 * n - flow.max_flow(s, t) << '\n';
end_clock();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
input:
5 2 3 6 7 1 9 5 10 4 8
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 4ms
memory: 5456kb
input:
5000 7985 7987 42 46 1591 1593 407 410 6305 6306 1456 1457 5874 5875 7135 7137 7041 7046 6813 6815 8868 8871 665 666 4055 4056 9789 9796 7067 7068 4745 4746 5167 5171 1735 1737 2125 2128 1444 1447 1348 1352 6087 6090 1381 1384 1600 1601 5187 5190 2801 2802 8449 8450 9376 9377 4021 4024 2674 2676 490...
output:
8134
result:
ok 1 number(s): "8134"
Test #3:
score: -100
Wrong Answer
time: 21ms
memory: 5444kb
input:
5000 3171 3172 4062 4064 4647 4651 3670 3673 7112 7114 9714 9717 3781 3789 8422 8426 457 460 5450 5454 7113 7122 6313 6320 9969 9973 828 832 6878 6892 4476 4483 892 903 251 259 6304 6315 130 134 9206 9215 2679 2686 9090 9091 8222 8228 9374 9375 2985 2989 3397 3401 4916 4918 6819 6821 883 889 2516 25...
output:
6962
result:
wrong answer 1st numbers differ - expected: '7047', found: '6962'