QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#84416 | #5668. Cell Nuclei Detection | jeffqi | WA | 342ms | 164024kb | C++14 | 2.4kb | 2023-03-06 14:46:42 | 2023-03-06 14:46:59 |
Judging History
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'