QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#84416#5668. Cell Nuclei DetectionjeffqiWA 342ms164024kbC++142.4kb2023-03-06 14:46:422023-03-06 14:46:59

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-06 14:46:59]
  • 评测
  • 测评结果:WA
  • 用时:342ms
  • 内存:164024kb
  • [2023-03-06 14:46:42]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for (int i = (a); i <= (b); ++i)
#define drep(i,a,b) for (int i = (a); i >= (b); --i)
#define grep(i,u) for (int i = head[u],v = e[i].v; i; v = e[i = e[i].nxt].v)
#define LL long long
#define pii pair<int,int>
#define pll pair<LL,LL>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
LL read() {
	LL x = 0,y = 1; char ch = getchar(); while (!isdigit(ch)) {if (ch == '-') y = -y; ch = getchar();}
	while (isdigit(ch)) {x = x*10+ch-'0'; ch = getchar();} return x*y;
}
namespace qiqi {
	const int N = 5e6+5,M = 2005,INF = 0x3f3f3f3f; int n,m,s,t,ecnt,cur[N],head[N],dep[N];
	vector<int> p[M][M]; struct Data {int x0,y0,x1,y1;} a[N]; struct Edge {int v,f,nxt;} e[N];
	void add(int u,int v,int f) {e[++ecnt] = (Edge){v,f,head[u]}; head[u] = ecnt;}
	void f_add(int u,int v,int f) {add(u,v,f); add(v,u,0);}
	bool bfs(int s,int t) {
		rep(i,1,t) {cur[i] = head[i]; dep[i] = 0;}
		queue<int> q; dep[s] = 1; q.push(s);
		while (!q.empty()) {
			int u = q.front(); q.pop();
			grep(i,u) if (!dep[v] && e[i].f) {
				dep[v] = dep[u]+1; q.push(v);
			}
		}
		return dep[t] != 0;
	}
	int dfs(int u,int t,int f) {
		if (!f || u == t) return f; int res = 0,k;
		for (int &i = cur[u],v = e[i].v; i; v = e[i = e[i].nxt].v) {
			if (dep[v] == dep[u]+1 && (k = dfs(v,t,min(f,e[i].f)))) {
				res += k; f -= k; e[i].f -= k; e[i^1].f += k; if (!f) break;
			}
		}
		return res;
	}
	int Dinic(int s,int t) {int res = 0; while (bfs(s,t)) res += dfs(s,t,INF); return res;}
	void main() {
		n = read(); m = read(); s = n+m+1; t = s+1;
		ecnt = 1; rep(i,1,t) head[i] = 0;
		rep(i,1,n) {
			int x0 = read(),y0 = read(),x1 = read(),y1 = read();
			a[i] = (Data){x0,y0,x1,y1}; f_add(s,i,1);
			rep(j,x0-1,x1+1) rep(k,y0-1,y1+1) p[j][k].eb(i);
		}
		rep(i,n+1,n+m) {
			int x0 = read(),y0 = read(),x1 = read(),y1 = read(); f_add(i,t,1);
			for (auto j:p[x0+((x1-x0)>>1)][y0+((y1-y0)>>1)]) if (a[j].x1 >= x0 && x1 >= a[j].x0 && a[j].y1 >= y0 && y1 >= a[j].y0) {
				if ((min(x1,a[j].x1)-max(x0,a[j].x0)+1)*(min(y1,a[j].y1)-max(y0,a[j].y0)+1)*2 >= (a[j].x1-a[j].x0+1)*(a[j].y1-a[j].y0+1)) f_add(j,i,1);
			}
		}
		rep(i,1,n) rep(j,a[i].x0-1,a[i].x1+1) rep(k,a[i].y0-1,a[i].y1+1) p[j][k].clear();
		printf("%d\n",Dinic(s,t));
	}
}
int main() {
	int T = read(); while (T--) qiqi::main(); return 0;
}

详细

Test #1:

score: 100
Accepted
time: 18ms
memory: 98068kb

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: 22ms
memory: 97756kb

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: 0
Accepted
time: 319ms
memory: 156212kb

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:

50000
50000
0
50000
3150

result:

ok 5 lines

Test #4:

score: -100
Wrong Answer
time: 342ms
memory: 164024kb

input:

5
50000 50000
0 0 1 1
1 0 2 1
2 0 3 1
3 0 4 1
4 0 5 1
5 0 6 1
6 0 7 1
7 0 8 1
8 0 9 1
9 0 10 1
10 0 11 1
11 0 12 1
12 0 13 1
13 0 14 1
14 0 15 1
15 0 16 1
16 0 17 1
17 0 18 1
18 0 19 1
19 0 20 1
20 0 21 1
21 0 22 1
22 0 23 1
23 0 24 1
24 0 25 1
25 0 26 1
26 0 27 1
27 0 28 1
28 0 29 1
29 0 30 1
30 0 ...

output:

50000
28200
12500
18000
8000

result:

wrong answer 2nd lines differ - expected: '25050', found: '28200'