QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#111784#5668. Cell Nuclei Detectionxaphoenix#RE 52ms109252kbC++143.4kb2023-06-08 19:23:032023-06-08 19:23:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-08 19:23:04]
  • 评测
  • 测评结果:RE
  • 用时:52ms
  • 内存:109252kb
  • [2023-06-08 19:23:03]
  • 提交

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

output:


result: