QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#180570 | #5668. Cell Nuclei Detection | arseny_y | TL | 43ms | 105656kb | C++23 | 2.7kb | 2023-09-16 00:20:08 | 2023-09-16 00:20:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(), (a).end()
#define X first
#define Y second
const ll INF = LLONG_MAX;
const int MOD = 1e9 + 7, MAXN = 2e5 + 1337;
const ld EPS = 1e-6;
void solve();
int main() {
#ifdef LOCAL
freopen("../main_cpp/input.txt", "r", stdin);
#else
cin.tie(nullptr)->sync_with_stdio(false);
#endif
int _ = 1;
cin >> _;
while (_--) {
solve();
}
}
vector<int> g[MAXN];
struct Rect {
int x1, y1, x2, y2;
int sq() {
if (min(x2 - x1 + 1, y2 - y1 + 1) <= 0) return 0;
return (x2 - x1 + 1) * (y2 - y1 + 1);
}
int intersec(const Rect oth) const {
Rect ans;
ans.x1 = max(x1, oth.x1);
ans.y1 = max(y1, oth.y1);
ans.x2 = min(x2, oth.x2);
ans.y2 = min(y2, oth.y2);
return ans.sq();
}
};
const int MX = 2000 + 10;
vector<int> have[MX][MX];
vector<int> py(MAXN, -1), px(MAXN, -1), usd(MAXN, 0), in(MAXN, false);
int timer = 1;
bool dfs(int v) {
if (++in[v] >= 5000) return false;
usd[v] = timer;
for (auto &to: g[v]) {
if (px[to] == -1 || usd[px[to]] != timer && dfs(px[to])) {
px[to] = v;
py[v] = to;
return true;
}
}
return false;
}
void solve() {
for (int i = 1; i < MX; ++i) for (int j = 1; j < MX; ++j) have[i][j].clear();
for (int i = 0; i < MAXN; ++i) {
py[i] = px[i] = -1;
usd[i] = in[i] = 0;
}
int n, m;
cin >> n >> m;
int sz = n + m + 10;
for (int i = 1; i <= sz; ++i) g[i].clear();
vector<Rect> a(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
for (int x = a[i].x1; x <= a[i].x2; ++x) {
for (int y = a[i].y1; y <= a[i].y2; ++y) {
have[x][y].push_back(i);
}
}
}
for (int i = 1; i <= m; ++i) {
int ind = i + n;
Rect cur;
cin >> cur.x1 >> cur.y1 >> cur.x2 >> cur.y2;
for (int x = cur.x1; x <= cur.x2; ++x) {
for (int y = cur.y1; y <= cur.y2; ++y) {
for (auto &el : have[x][y]) {
if (a[el].intersec(cur) * 2 >= a[el].sq()) {
g[el].push_back(ind);
g[ind].push_back(el);
}
}
}
}
}
for (auto &el : g) {
sort(all(el)), el.resize(unique(all(el)) - el.begin());
}
int ans = 0;
for (int i = 1; i <= n; ++i) ans += dfs(i), ++timer;
cout << ans << "\n";
}
详细
Test #1:
score: 100
Accepted
time: 37ms
memory: 105644kb
input:
3 2 2 1 1 3 3 3 3 5 5 2 2 4 4 4 4 6 6 2 3 1 1 3 3 3 3 5 5 1 3 3 5 2 1 4 5 3 1 5 3 3 3 1 1 2 2 2 2 3 3 3 3 4 4 1 1 3 3 2 2 4 4 3 3 5 5
output:
0 1 3
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 43ms
memory: 105656kb
input:
3 2 2 1 1 3 3 3 3 5 5 2 2 4 4 4 4 6 6 2 3 1 1 3 3 3 3 5 5 1 3 3 5 2 1 4 5 3 1 5 3 3 3 1 1 2 2 2 2 3 3 3 3 4 4 1 1 3 3 2 2 4 4 3 3 5 5
output:
0 1 3
result:
ok 3 lines
Test #3:
score: -100
Time Limit Exceeded
input:
5 50000 50000 0 0 4 4 4 0 8 4 8 0 12 4 12 0 16 4 16 0 20 4 20 0 24 4 24 0 28 4 28 0 32 4 32 0 36 4 36 0 40 4 40 0 44 4 44 0 48 4 48 0 52 4 52 0 56 4 56 0 60 4 60 0 64 4 64 0 68 4 68 0 72 4 72 0 76 4 76 0 80 4 80 0 84 4 84 0 88 4 88 0 92 4 92 0 96 4 96 0 100 4 100 0 104 4 104 0 108 4 108 0 112 4 112 ...