fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int, int> pi;
  4. typedef long long lint;
  5.  
  6. const int MAXN = 222222;
  7. struct maxflow{
  8. 	struct edg{int pos, cap, rev, idx;};
  9. 	vector<edg> gph[MAXN];
  10.  
  11. 	void clear(){
  12. 		for(int i=0; i<MAXN; i++){
  13. 			gph[i].clear();
  14. 		}
  15. 	}
  16.  
  17. 	void add_edge(int s, int e, int x){
  18. 		gph[s].push_back({e, x, (int)gph[e].size(), -1});
  19. 		gph[e].push_back({s, 0, (int)gph[s].size()-1, -1});
  20. 	}
  21.  
  22. 	void add_edge(int s, int e, int x, int idx){
  23. 		gph[s].push_back({e, x, (int)gph[e].size(), idx});
  24. 		gph[e].push_back({s, 0, (int)gph[s].size()-1, -1});
  25. 	}
  26.  
  27. 	int dis[MAXN], pnt[MAXN];
  28.  
  29. 	bool bfs(int src, int sink){
  30. 		memset(dis, 0, sizeof(dis));
  31. 		memset(pnt, 0, sizeof(pnt));
  32. 		queue<int> que;
  33. 		que.push(src);
  34. 		dis[src] = 1;
  35. 		while(!que.empty()){
  36. 			int x = que.front();
  37. 			que.pop();
  38. 			for(int i=0; i<gph[x].size(); i++){
  39. 				edg e = gph[x][i];
  40. 				if(e.cap > 0 && !dis[e.pos]){
  41. 					dis[e.pos] = dis[x] + 1;
  42. 					que.push(e.pos);
  43. 				}
  44. 			}
  45. 		}
  46. 		return dis[sink] > 0;
  47. 	}
  48.  
  49. 	int dfs(int x, int sink, int f){
  50. 		if(x == sink) return f;
  51. 		for(; pnt[x] < gph[x].size(); pnt[x]++){
  52. 			edg e = gph[x][pnt[x]];
  53. 			if(e.cap > 0 && dis[e.pos] == dis[x] + 1){
  54. 				int w = dfs(e.pos, sink, min(f, e.cap));
  55. 				if(w){
  56. 					gph[x][pnt[x]].cap -= w;
  57. 					gph[e.pos][e.rev].cap += w;
  58. 					return w;
  59. 				}
  60. 			}
  61. 		}
  62. 		return 0;
  63. 	}
  64.  
  65. 	lint match(int src, int sink){
  66. 		lint ret = 0;
  67. 		while(bfs(src, sink)){
  68. 			int r;
  69. 			while((r = dfs(src, sink, 2e9))) ret += r;
  70. 		}
  71. 		return ret;
  72. 	}
  73. }maxflow;
  74.  
  75. int n, m, sx, sy;
  76. int x[100005], y[100005];
  77. pi nx[100005], ny[100005];
  78.  
  79. string solve(){
  80. 	int src = sx + sy;
  81. 	int snk = sx + sy + 1;
  82. 	int asrc = sx + sy + 2;
  83. 	int asnk = sx + sy + 3;
  84. 	lint s1 = 0, s2 = 0;
  85. 	for(int i=0; i<sx; i++){
  86. 		s1 += nx[i].first;
  87. 		maxflow.add_edge(asrc, i, nx[i].second - nx[i].first);
  88. 		maxflow.add_edge(asrc, snk, nx[i].first);
  89. 		maxflow.add_edge(src, i, nx[i].first);
  90. 	}
  91. 	for(int i=0; i<sy; i++){
  92. 		s2 += ny[i].first;
  93. 		maxflow.add_edge(sx + i, asnk, ny[i].second - ny[i].first);
  94. 		maxflow.add_edge(sx + i, snk, ny[i].first);
  95. 		maxflow.add_edge(src, asnk, ny[i].first);
  96. 	}
  97. 	for(int i=0; i<n; i++){
  98. 		maxflow.add_edge(x[i], y[i] + sx, 1, i);
  99. 	}
  100. 	maxflow.add_edge(asnk, asrc, 1e9);
  101. 	if(maxflow.match(src, snk) != s1 + s2) return "-1";
  102. 	maxflow.match(asrc, asnk);
  103. 	string ret(n, 'a');
  104. 	for(int i=0; i<sx; i++){
  105. 		for(auto &j : maxflow.gph[i]){
  106. 			if(j.idx != -1){
  107. 				if(j.cap == 0) ret[j.idx] = 'b';
  108. 				else ret[j.idx] = 'r';
  109. 			}
  110. 		}
  111. 	}
  112. 	return ret;
  113. }
  114.  
  115. int cnt1[100005], cnt2[100005];
  116.  
  117. int main(){
  118. 	vector<int> vx, vy;
  119. 	int r, b;
  120. 	cin >> n >> m >> r >> b;
  121. 	for(int i=0; i<n; i++){
  122. 		scanf("%d %d",&x[i],&y[i]);
  123. 		vx.push_back(x[i]);
  124. 		vy.push_back(y[i]);
  125. 	}
  126. 	sort(vx.begin(), vx.end());
  127. 	sort(vy.begin(), vy.end());
  128. 	vx.resize(unique(vx.begin(), vx.end()) - vx.begin());
  129. 	vy.resize(unique(vy.begin(), vy.end()) - vy.begin());
  130. 	for(int i=0; i<n; i++){
  131. 		x[i] = lower_bound(vx.begin(), vx.end(), x[i]) - vx.begin();
  132. 		y[i] = lower_bound(vy.begin(), vy.end(), y[i]) - vy.begin();
  133. 		nx[x[i]].second++;
  134. 		ny[y[i]].second++;
  135. 		cnt1[x[i]]++;
  136. 		cnt2[y[i]]++;
  137. 	}	
  138. 	sx = vx.size();
  139. 	sy = vy.size();
  140. 	for(int i=0; i<m; i++){
  141. 		int t, l, d;
  142. 		scanf("%d %d %d",&t,&l,&d);
  143. 		if(t == 1){
  144. 			auto p = lower_bound(vx.begin(), vx.end(), l);
  145. 			if(p == vx.end() || *p != l) continue;
  146. 			int idx = p - vx.begin();
  147. 			nx[idx].first = max(nx[idx].first, (cnt1[idx] - d + 1) / 2);
  148. 			nx[idx].second = min(nx[idx].second, (cnt1[idx] + d) / 2);
  149. 			if(nx[idx].first > nx[idx].second){
  150. 				puts("-1");
  151. 				return 0;
  152. 			}
  153. 		}
  154. 		else{
  155. 			auto p = lower_bound(vy.begin(), vy.end(), l);	
  156. 			if(p == vy.end() || *p != l) continue;
  157. 			int idx = p - vy.begin();
  158. 			ny[idx].first = max(ny[idx].first, (cnt2[idx] - d + 1) / 2);
  159. 			ny[idx].second = min(ny[idx].second, (cnt2[idx] + d) / 2);
  160. 			if(ny[idx].first > ny[idx].second){
  161. 				puts("-1");
  162. 				return 0;
  163. 			}
  164. 		}
  165. 	}
  166. 	auto w = solve();
  167. 	if(w == "-1"){
  168. 		puts("-1");
  169. 		return 0;
  170. 	}
  171. 	if(r < b){
  172. 		for(auto &i : w) i ^= ('r' ^ 'b');
  173. 	}
  174. 	lint ret = 0;
  175. 	for(auto &i : w){
  176. 		if(i == 'r') ret += r;
  177. 		else ret += b;
  178. 	}
  179. 	printf("%lld\n", ret);
  180. 	cout << w << endl;
  181. }
Success #stdin #stdout 0s 10952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/thLlg8
language:
C++14 (gcc 8.3)
created:
7 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!