QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#111784 | #5668. Cell Nuclei Detection | xaphoenix# | RE | 52ms | 109252kb | C++14 | 3.4kb | 2023-06-08 19:23:03 | 2023-06-08 19:23:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define LC k<<1
#define RC k<<1|1
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i,a,n) for (int i = a; i < n; i++)
#define repn(i,a,n) for (int i = a; i <= n; i++)
#define per(i,a,n) for (int i = (n) - 1; i >= a; i--)
#define pern(i,a,n) for (int i = n; i >= a; i--)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
typedef pair<double, double> PDD;
typedef pair<ull, ull> PUU;
typedef pair<LL, LL> PLL;
const int N = 110000;
const int M = 1100000;
const int mod = 1e9+7;
const int inf = (int)1e9;
const LL INF = 1e18;
const double eps = 1e-9;
mt19937_64 Rand((unsigned long long)new char);
#define rand Rand
struct rec {
int x1, y1, x2, y2, id;
void read(int _id) {
id = _id;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);
}
int area() {
return (x2 - x1) * (y2 - y1);
}
}gt[N], dt[N];
int check(rec dt, rec gt) {
int x1 = max(dt.x1, gt.x1), x2 = min(dt.x2, gt.x2);
int y1 = max(dt.y1, gt.y1), y2 = min(dt.y2, gt.y2);
int area = max(x2 - x1, 0) * max(y2 - y1, 0);
return 2 * area >= gt.area();
}
int T, n, m;
struct MCMF {
// bfs, dinic
// st must be the lowest index, ed must be the highest index
int e[M], f[M], pre[M], last[N];
int d[N], now[N];
int num, st, ed, maxflow;
queue<int> q;
void init() {
num = 1;
repn(i, st, ed) last[i] = 0;
maxflow = 0;
}
void insert(int x, int y, int z) {
e[++num] = y, f[num] = z, pre[num] = last[x], last[x] = num;
e[++num] = x, f[num] = 0, pre[num] = last[y], last[y] = num;
}
bool bfs() {
memset(d, -1, sizeof(d));
d[st] = 0;
q.push(st);
while(!q.empty()) {
int now = q.front();
for (int i = last[now]; i; i = pre[i]) if (f[i] && d[e[i]] == -1) {
d[e[i]] = d[now] + 1;
q.push(e[i]);
}
q.pop();
}
if (d[ed] == -1) return 0;
return 1;
}
int dfs(int x, int incf) {
if (x == ed) return incf;
int flow = 0, w;
for (int i = now[x]; i; i = pre[i]) if (f[i] && d[e[i]] == d[x] + 1) {
w = dfs(e[i], min(incf - flow, f[i]));
f[i] -= w, f[i ^ 1] += w; flow += w;
if (f[i]) now[x] = i;
if (flow == incf) return incf;
}
if (!flow) d[x] = -1;
return flow;
}
void run() {
while(bfs()) {
repn(i, st, ed) now[i] = last[i];
maxflow += dfs(st, inf);
}
}
}solver;
const int L = 2100;
vector<rec> f[L][L];
int main() {
IO;
cin >> T;
while (T--) {
cin >> m >> n;
rep(i, 0, L) rep(j, 0, L) f[i][j].clear();
solver.st = 0, solver.ed = n + m + 1;
solver.init();
repn(i, 1, m) {
gt[i].read(i + n);
f[gt[i].x1][gt[i].y1].pb(gt[i]);
solver.insert(i + n, n + m + 1, 1);
}
repn(i, 1, n) {
dt[i].read(i);
solver.insert(0, i, 1);
repn(x, -4, 4) repn(y, -4, 4) {
int nx = dt[i].x1 + x, ny = dt[i].y1 + y;
if (nx < 0 || nx > L || ny < 0 || ny > L) continue;
for (auto p: f[nx][ny]) {
if (check(dt[i], p)) solver.insert(i, p.id, 1);
}
}
}
solver.run();
cout << solver.maxflow << "\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 52ms
memory: 109252kb
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: 52ms
memory: 108772kb
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
Runtime Error
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 ...