QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#180570#5668. Cell Nuclei Detectionarseny_yTL 43ms105656kbC++232.7kb2023-09-16 00:20:082023-09-16 00:20:09

Judging History

你现在查看的是最新测评结果

  • [2023-09-16 00:20:09]
  • 评测
  • 测评结果:TL
  • 用时:43ms
  • 内存:105656kb
  • [2023-09-16 00:20:08]
  • 提交

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 ...

output:


result: