QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90900 | #5668. Cell Nuclei Detection | Mr_Eight | AC ✓ | 3017ms | 127852kb | C++23 | 3.6kb | 2023-03-26 02:29:15 | 2023-03-26 02:29:17 |
Judging History
answer
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <functional>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <complex>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define itn int
#define nit int
#define ll long long
#define ms multiset
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define re register
#define ri re int
#define il inline
#define pii pair<int,int>
#define cp complex<double>
//#pra gma G CC opti mize(3)
using namespace std;
using std::bitset;
//using namespace __gnu_pbds;
const double Pi=acos(-1);
namespace fastIO {
template<class T>
inline void read(T &x) {
x=0;
bool fu=0;
char ch=0;
while(ch>'9'||ch<'0') {
ch=getchar();
if(ch=='-')fu=1;
}
while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
if(fu)x=-x;
}
inline int read() {
int x=0;
bool fu=0;
char ch=0;
while(ch>'9'||ch<'0') {
ch=getchar();
if(ch=='-')fu=1;
}
while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
return fu?-x:x;
}
char _n_u_m_[40];
template<class T>
inline void write(T x ) {
if(x==0){
putchar('0');
return;
}
T tmp = x > 0 ? x : -x ;
if( x < 0 ) putchar('-') ;
register int cnt = 0 ;
while( tmp > 0 ) {
_n_u_m_[ cnt ++ ] = tmp % 10 + '0' ;
tmp /= 10 ;
}
while( cnt > 0 ) putchar(_n_u_m_[ -- cnt ]) ;
}
template<class T>
inline void write(T x ,char ch) {
write(x);
putchar(ch);
}
}
using namespace fastIO;
const int MAXN=100002,MAXM=1000002;
int cnt=1,S,T=MAXN-1,head[MAXN],deep[MAXN],to[MAXM<<1],v[MAXM<<1],nxt[MAXM<<1],now[MAXN];
inline void clear(){
cnt=1;
memset(head,0,sizeof(head));
memset(deep,0,sizeof(deep));
memset(to,0,sizeof(to));
memset(v,0,sizeof(v));
memset(nxt,0,sizeof(nxt));
memset(now,0,sizeof(now));
}
inline void add(int x,int y,int vv){
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
v[cnt]=vv;
}inline void ed(int x,int y,int vv){
add(x,y,vv);
add(y,x,0);
}
inline bool bfs(){
memset(deep,0,sizeof(deep));
deep[S]=1;
queue<int>q;
q.push(S);
ri h;
while(!q.empty()){
h=q.front();
q.pop();
now[h]=head[h];
for(ri i=head[h];i;i=nxt[i]){
if(!deep[to[i]]&&v[i]>0){
q.push(to[i]);
deep[to[i]]=deep[h]+1;
}
}
}return deep[T];
}
inline int dfs(int pos,int mmax){
if(pos==T)return mmax;
ri rt=0;
for(ri i=now[pos];i&&mmax;i=nxt[i]){
now[pos]=i;
if(deep[to[i]]==deep[pos]+1&&v[i]>0){
ri k=dfs(to[i],min(mmax,v[i]));
if(k==0)deep[to[i]]=INT_MAX-2;
else{
rt+=k;
mmax-=k;
v[i]-=k;
v[i^1]+=k;
}
}
}return rt;
}
inline int Dinic(){
ri rt=0;
while(bfs()){
rt+=dfs(S,INT_MAX);
}return rt;
}
vector<pair<pii,int> >p[2002][2002];
int main(){
F(asdff,1,read()){
clear();
int n=read(),m=read();
F(i,0,2000)F(j,0,2000)p[i][j].clear();
F(i,1,n){
int x=read(),y=read();
int v=read(),u=read();
p[x][y].emplace_back(pii{v,u},i);
}
F(i,1,m){
int a=read(),b=read(),c=read(),d=read();
F(x,max(0,a-2),c-1)F(y,max(0,b-2),d-1){
for(auto u:p[x][y]){
int z=u.first.first,w=u.first.second;
if((z-x)*(w-y)<=2*max(0,min(c,z)-max(a,x))*max(0,min(d,w)-max(b,y)))ed(i+n,u.second,1);
}
}
}
F(i,1,n)ed(i,T,1);
F(i,n+1,n+m)ed(S,i,1);
write(Dinic(),'\n');
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 49ms
memory: 121860kb
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: 57ms
memory: 121848kb
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: 1529ms
memory: 125112kb
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: 0
Accepted
time: 222ms
memory: 127852kb
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 25050 12500 16000 8000
result:
ok 5 lines
Test #5:
score: 0
Accepted
time: 233ms
memory: 123764kb
input:
5 50000 50000 0 0 2 4 4 0 7 1 8 0 10 1 12 0 15 3 16 0 19 1 20 0 22 2 24 0 26 4 28 0 30 4 32 0 36 3 36 0 40 1 40 0 44 1 44 0 47 2 48 0 49 3 52 0 54 1 56 0 59 4 60 0 64 3 64 0 68 3 68 0 70 1 72 0 76 4 76 0 80 3 80 0 84 4 84 0 87 2 88 0 90 1 92 0 94 4 96 0 98 1 100 0 104 1 104 0 107 2 108 0 110 4 112 0...
output:
10594 10779 10618 10381 10779
result:
ok 5 lines
Test #6:
score: 0
Accepted
time: 3017ms
memory: 123608kb
input:
5 50000 50000 0 0 4 4 1 0 5 4 2 0 6 4 3 0 7 4 4 0 8 4 5 0 9 4 6 0 10 4 7 0 11 4 8 0 12 4 9 0 13 4 10 0 14 4 11 0 15 4 12 0 16 4 13 0 17 4 14 0 18 4 15 0 19 4 16 0 20 4 17 0 21 4 18 0 22 4 19 0 23 4 20 0 24 4 21 0 25 4 22 0 26 4 23 0 27 4 24 0 28 4 25 0 29 4 26 0 30 4 27 0 31 4 28 0 32 4 29 0 33 4 30...
output:
50000 50000 50000 50000 49600
result:
ok 5 lines
Test #7:
score: 0
Accepted
time: 35ms
memory: 121900kb
input:
1 4 4 1 1 3 3 2 1 4 3 1 2 3 4 2 2 4 4 2 1 4 3 3 2 5 4 1 2 3 4 2 3 4 5
output:
3
result:
ok single line: '3'