fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int Long;
  4. //typedef long long int ll;
  5. typedef int ll;
  6. typedef ll ft;
  7. typedef set<int> si;
  8. typedef long long Long;
  9. typedef vector<int> vi;
  10. typedef vector<vi> vii;
  11. typedef vector<Long>vl;
  12. typedef pair<int,int>pii;
  13. typedef pair<Long,Long>pll;
  14. typedef pair<string,int>psi;
  15. typedef pair<double,double>pdd;
  16. #define get getchar_unlocked
  17. #define put putchar_unlocked
  18. #define pb push_back
  19. #define mp make_pair
  20. #define ff first
  21. #define ss second
  22. #define sz size()
  23. #define ln length()
  24. #define repstl(i, s) for (__typeof((s).end())i=(s).begin();i!=(s).end();++i)
  25. #define debug1(s,a) cout << s << " " << a << " " << endl;
  26. #define debug2(s,a,b) cout << s << " " << a << " " << b << " " << endl
  27. #define debug3(s,a,b,c) cout << s << " " << a << " " << b << " " << c << " " << endl;
  28. #define debug4(s,a,b,c,d) cout << s << " " << a << " " << b << " " << c << " " << d << " " << endl;
  29. #define debug5(s,a,b,c,d,e) cout << s << " " << a << " " << b << " " << c << " " << d << " " << e << " " << endl;
  30. #define PI 3.1415926535897932384626433832795
  31. #define FO freopen ("out.txt", "w", stdout)
  32. #define FI freopen ("in.txt", "r", stdin)
  33. #define ref(i,a,n) for(int i=a;i<=n;i++)
  34. #define reb(i,n,a) for(int i=n;i>=a;i--)
  35. #define rep(i,n) for(int i=0;i<n;i++)
  36. #define all(a) a.begin(),a.end()
  37. #define gi(n) scanf("%d",&n)
  38. #define gii(n) scanf("%lld",&n)
  39. #define gc(c) scanf(" %c",&c)
  40. #define gs(s) scanf(" %s",s);
  41. #define pi(n) printf("%d",n)
  42. #define pii(n) printf("%lld",n)
  43. #define pc(c) printf("%c",c)
  44. #define ps printf(" ")
  45. #define pn printf("\n")
  46. #define pl(a) printf("%s",a)
  47. #define l(a) 2*a+1
  48. #define r(a) 2*a+2
  49. #define left(a,b) a,(a+b)/2
  50. #define right(a,b) (a+b)/2+1,b
  51. #define mid(a,b) (a+b)/2
  52. void gl(char *str){register char c=0;register int i=0;while(c<33)c=get();while(c!='\n'){str[i]=c;c=get();i=i+1;}str[i]='\0';}
  53. void gfi(ft &x) {register ft c = get(); x = 0; ft sn=1;for(;(c<48 || c>57);c = get()) if(c=='-') sn=-1;for(;c>47 && c<58;c = get()) {x = (x<<1) + (x<<3) + c - 48;}x*=sn;}
  54. //int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
  55. //int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
  56. //int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
  57. //int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction
  58.  
  59. #define E 401*251
  60. #define MAX numeric_limits<ll>::max()
  61. ll to[E],next[E],fin[E],flow[E],cap[E],dist[E],pro[E],nEdge,nNode,src,snk,N;
  62.  
  63. void init(ll _nNode,ll _src,ll _snk) {
  64. 	src=_src;snk=_snk;
  65. 	nNode=_nNode;nEdge=0;
  66. 	rep(i,nNode+1) fin[i]=-1;
  67. }
  68.  
  69. void add(ll u,ll v) {
  70. 	to[nEdge]=u; cap[nEdge]=1; flow[nEdge]=0; next[nEdge]=fin[v]; fin[v]=nEdge++;
  71. 	to[nEdge]=v; cap[nEdge]=1; flow[nEdge]=0; next[nEdge]=fin[u]; fin[u]=nEdge++;
  72. }
  73.  
  74. struct node {
  75. 	ll x,y;
  76. }P[E],T[E];
  77.  
  78. typedef struct node nod;
  79.  
  80. ll D(nod a,nod b) {
  81. //	cout << a.x << " " << a.y << " " << b.x << " " << b.y << endl;
  82. 	return abs(a.x-b.x)+abs(a.y-b.y);
  83. }
  84.  
  85. ll bfs() {
  86. 	queue<ll> q;
  87. 	dist[src]=0;
  88. 	q.push(src);
  89. 	ref(i,1,nNode) dist[i]=-1;
  90. 	while(!q.empty()) {
  91. 		ll u=q.front();
  92. 		q.pop();
  93. 		for(int i=fin[u];i>=0;i=next[i]) {
  94. 			ll v=to[i];
  95. 			if(dist[v]==-1 && (cap[i]-flow[i])>0) dist[v]=dist[u]+1,q.push(v);
  96. 		}
  97. 	}
  98. 	return dist[snk]!=-1;
  99. }
  100.  
  101. ll dfs(ll u,ll d) {
  102. 	if(u==snk) return d;
  103. 	for(int &i=pro[u];i>=0;i=next[i]) {
  104. 		ll v=to[i];
  105. 		if((cap[i]-flow[i])>0 && dist[v]==dist[u]+1) {
  106. 			ll temp=dfs(v,min(d,cap[i]-flow[i]));
  107. 			if(temp>0) {
  108. 				flow[i]+=temp;
  109. 				flow[i^1]-=temp;
  110. 				return temp;
  111. 			}
  112. 		}
  113. 	}
  114. 	return 0;
  115. }
  116.  
  117. ll dinitz() {
  118. 	ll ans=0;
  119. 	while(bfs()) {
  120. 		rep(i,nNode+1) pro[i]=fin[i];
  121. 		while(1) {
  122. 			ll temp=dfs(src,MAX);
  123. 			if(temp) ans+=temp; else break;
  124. 		}
  125. 	}
  126. 	return ans;
  127. }
  128.  
  129. int main() {
  130. 	ll t;
  131. 	gfi(t);
  132. 	while(t--) {
  133. 		ll n,m,s,c;
  134. 		gfi(n);gfi(m);gfi(s);gfi(c);
  135. 		N=n+m+1;
  136. 		init(N,0,N);
  137. 		ref(i,1,n) add(0,i);
  138. 		ref(i,n+1,n+m) add(i,n+m+1);
  139. 		rep(i,n) gfi(P[i].x),gfi(P[i].y);
  140. 		rep(i,m) gfi(T[i].x),gfi(T[i].y);
  141. 		rep(i,n) rep(j,m) {
  142. //			cout << "dist: " << D(P[i],T[j]) << " " << (s*c)/200 << endl;
  143. 			if(D(P[i],T[j])<=(s*c)/200) {
  144. //				cout << "add: " << i+1 << " " << j+1 << endl;
  145. 				add(i+1,j+1+n);
  146. 			}
  147. 		}
  148. 		pi(dinitz());pn;
  149. 	}
  150. 	return 0;
  151. }
  152.  
Time limit exceeded #stdin #stdout 5s 7468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ereEXE
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!