QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#90900#5668. Cell Nuclei DetectionMr_EightAC ✓3017ms127852kbC++233.6kb2023-03-26 02:29:152023-03-26 02:29:17

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-26 02:29:17]
  • 评测
  • 测评结果:AC
  • 用时:3017ms
  • 内存:127852kb
  • [2023-03-26 02:29:15]
  • 提交

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'