fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. #include <ext/rope>
  6. using namespace __gnu_pbds;
  7. using namespace __gnu_cxx;
  8. #ifndef rd
  9. #define trace(...)
  10. #define endl '\n'
  11. #endif
  12. #define pb push_back
  13. #define fi first
  14. #define se second
  15. #define int long long
  16. typedef long long ll;
  17. typedef long double f80;
  18. #define double long double
  19. #define pii pair<int,int>
  20. #define pll pair<ll,ll>
  21. #define sz(x) ((long long)x.size())
  22. #define fr(a,b,c) for(int a=b; a<=c; a++)
  23. #define rep(a,b,c) for(int a=b; a<c; a++)
  24. #define trav(a,x) for(auto &a:x)
  25. #define all(con) con.begin(),con.end()
  26. const ll infl=0x3f3f3f3f3f3f3f3fLL;
  27. const int infi=0x3f3f3f3f;
  28. //const int mod=998244353;
  29. const int mod=1000000007;
  30. typedef vector<int> vi;
  31. typedef vector<ll> vl;
  32.  
  33. typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
  34. auto clk=clock();
  35. mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
  36. int rng(int lim) {
  37. 	uniform_int_distribution<int> uid(0,lim-1);
  38. 	return uid(rang);
  39. }
  40. int powm(int a, int b) {
  41. 	int res=1;
  42. 	while(b) {
  43. 		if(b&1)
  44. 			res=(res*a)%mod;
  45. 		a=(a*a)%mod;
  46. 		b>>=1;
  47. 	}
  48. 	return res;
  49. }
  50.  
  51. long long readInt(long long l, long long r, char endd) {
  52. 	long long x=0;
  53. 	int cnt=0;
  54. 	int fi=-1;
  55. 	bool is_neg=false;
  56. 	while(true) {
  57. 		char g=getchar();
  58. 		if(g=='-') {
  59. 			assert(fi==-1);
  60. 			is_neg=true;
  61. 			continue;
  62. 		}
  63. 		if('0'<=g&&g<='9') {
  64. 			x*=10;
  65. 			x+=g-'0';
  66. 			if(cnt==0) {
  67. 				fi=g-'0';
  68. 			}
  69. 			cnt++;
  70. 			assert(fi!=0 || cnt==1);
  71. 			assert(fi!=0 || is_neg==false);
  72.  
  73. 			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
  74. 		} else if(g==endd) {
  75. 			if(is_neg) {
  76. 				x=-x;
  77. 			}
  78. 			assert(l<=x&&x<=r);
  79. 			return x;
  80. 		} else {
  81. 			assert(false);
  82. 		}
  83. 	}
  84. }
  85. string readString(int l, int r, char endd) {
  86. 	string ret="";
  87. 	int cnt=0;
  88. 	while(true) {
  89. 		char g=getchar();
  90. 		assert(g!=-1);
  91. 		if(g==endd) {
  92. 			break;
  93. 		}
  94. 		cnt++;
  95. 		ret+=g;
  96. 	}
  97. 	assert(l<=cnt&&cnt<=r);
  98. 	return ret;
  99. }
  100. long long readIntSp(long long l, long long r) {
  101. 	return readInt(l,r,' ');
  102. }
  103. long long readIntLn(long long l, long long r) {
  104. 	return readInt(l,r,'\n');
  105. }
  106. string readStringLn(int l, int r) {
  107. 	return readString(l,r,'\n');
  108. }
  109. string readStringSp(int l, int r) {
  110. 	return readString(l,r,' ');
  111. }
  112.  
  113. int sum_n=0,sum_m=0,sum_q=0;
  114. #define rsz(x, n) x.resize(n)
  115. #define clr(x) x.clear()
  116. class SCC {
  117. public:
  118. 	int n,cnt; // cnt -> number of scc's formed
  119. 	vector<vector<int>> g,rg,sg,comp; // sg -> dag with all nodes compressed.
  120. 	vector<int> scc,order;
  121. 	vector<bool> vis;
  122. 	void reset() {
  123. 		clr(g),clr(rg),clr(sg),clr(comp),clr(scc),clr(order),clr(vis);
  124. 	}
  125. 	void init(int _n) {
  126. 		reset();
  127. 		n=_n,cnt=0;
  128. 		_n+=2;
  129. 		rsz(g, _n),rsz(rg,_n),rsz(sg,_n),rsz(comp,_n);
  130. 		scc.resize(_n,0);
  131. 		vis.resize(_n,0);
  132. 	}
  133. 	void add(int u, int v) {
  134. 		g[u].push_back(v);
  135. 		rg[v].push_back(u);
  136. 	}
  137. 	void compute() {
  138. 		fr(i, 1, n)
  139. 			if(!vis[i])
  140. 				dfs1(i);
  141. 		fill(all(vis),0);
  142. 		for(int i=n-1; i>=0; i--)
  143. 			if(!vis[order[i]])
  144. 				dfs2(order[i],++cnt);
  145. 	}
  146. 	void dfs1(int u) {
  147. 		vis[u]=1;
  148. 		for(int v : g[u])
  149. 			if(!vis[v])
  150. 				dfs1(v);
  151. 		order.pb(u);
  152. 	}
  153. 	void dfs2(int u, int c) {
  154. 		vis[u]=1;
  155. 		scc[u]=c;
  156. 		comp[c].pb(u);
  157. 		for(int v : rg[u]) {
  158. 			if(!vis[v])
  159. 				dfs2(v,c);
  160. 			if(vis[v]&&c!=scc[v])
  161. 				sg[scc[v]].pb(c);
  162. 		}
  163. 	}
  164. };
  165.  
  166. struct Edge {
  167. 	int from,to,cap,flow,index;
  168. 	Edge(int from, int to, int cap, int flow, int index) :
  169. 			from(from), to(to), cap(cap), flow(flow), index(index) {
  170. 	}
  171. };
  172. struct PushRelabel {
  173. 	int N;
  174. 	vector<vector<Edge> > G;
  175. 	vector<ll> excess;
  176. 	vector<int> dist,active,count;
  177. 	queue<int> Q;
  178. 	PushRelabel(int N) :
  179. 			N(N), G(N), excess(N), dist(N), active(N), count(2*N) {
  180. 	}
  181. 	void AddEdge(int from, int to, int cap) {
  182. 		G[from].push_back(Edge(from,to,cap,0,G[to].size()));
  183. 		if(from==to)
  184. 			G[from].back().index++;
  185. 		G[to].push_back(Edge(to,from,0,0,G[from].size()-1)); // for bidirectional set cap.
  186. 	}
  187. 	void Enqueue(int v) {
  188. 		if(!active[v]&&excess[v]>0) {
  189. 			active[v]=true;
  190. 			Q.push(v);
  191. 		}
  192. 	}
  193. 	void Push(Edge &e) {
  194. 		int amt=min(excess[e.from],ll(e.cap-e.flow));
  195. 		if(dist[e.from]<=dist[e.to]||amt==0)
  196. 			return;
  197. 		e.flow+=amt;
  198. 		G[e.to][e.index].flow-=amt;
  199. 		excess[e.to]+=amt;
  200. 		excess[e.from]-=amt;
  201. 		Enqueue(e.to);
  202. 	}
  203. 	void Gap(int k) {
  204. 		fr(v, 0, N - 1) {
  205. 			if(dist[v]<k)
  206. 				continue;
  207. 			count[dist[v]]--;
  208. 			dist[v]=max(dist[v],N+1);
  209. 			count[dist[v]]++;
  210. 			Enqueue(v);
  211. 		}
  212. 	}
  213. 	void Relabel(int v) {
  214. 		count[dist[v]]--;
  215. 		dist[v]=2*N;
  216. 		fr(i, 0, G[v].size() - 1)
  217. 			if(G[v][i].cap-G[v][i].flow>0)
  218. 				dist[v]=min(dist[v],dist[G[v][i].to]+1);
  219. 		count[dist[v]]++;
  220. 		Enqueue(v);
  221. 	}
  222. 	void Discharge(int v) {
  223. 		for(int i=0; excess[v]>0&&i<G[v].size(); i++)
  224. 			Push(G[v][i]);
  225. 		if(excess[v]>0) {
  226. 			if(count[dist[v]]==1) {
  227. 				Gap(dist[v]);
  228. 			}
  229. 			else
  230. 				Relabel(v);
  231. 		}
  232. 	}
  233. 	ll GetMaxFlow(int s, int t) {
  234. 		count[0]=N-1;
  235. 		count[N]=1;
  236. 		dist[s]=N;
  237. 		active[s]=active[t]=1;
  238. 		fr(i, 0, (int)G[s].size() - 1) {
  239. 			excess[s]+=G[s][i].cap;
  240. 			Push(G[s][i]);
  241. 		}
  242. 		while(!Q.empty()) {
  243. 			int v=Q.front();
  244. 			Q.pop();
  245. 			active[v]=0;
  246. 			Discharge(v);
  247. 		}
  248. 		ll totflow=0;
  249. 		fr(i, 0, (int)G[s].size() - 1)
  250. 			totflow+=G[s][i].flow;
  251. 		return totflow;
  252. 	}
  253. };
  254. const int INF=infi;
  255. struct MaxFlowLowerBound {
  256. 	PushRelabel PR;
  257. 	int N,s,t,s1,t1;
  258. 	ll total_demands;
  259. 	MaxFlowLowerBound(int N, int s, int t) :
  260. 			N(N), PR(N+2), s(s), t(t), s1(N), t1(N+1), total_demands(0) {
  261. 		PR.AddEdge(t,s,INF);
  262. 	}
  263. 	void AddEdge(int from, int to, ll lo, ll hi) {
  264. 		PR.AddEdge(s1,to,lo);
  265. 		PR.AddEdge(from,t1,lo);
  266. 		PR.AddEdge(from,to,hi-lo);
  267. 		total_demands+=lo;
  268. 	}
  269. 	ll GetMaxFlow() {
  270. 		if(PR.GetMaxFlow(s1,t1)<total_demands)
  271. 			return -1;
  272. 		PushRelabel PR1(N);
  273. 		ll initial=0;
  274. 		for(int i=0; i<N; i++) {
  275. 			for(auto e : PR.G[i]) {
  276. 				if(e.flow<0||e.cap==0)
  277. 					continue;
  278. 				if(e.to>=N)
  279. 					continue;
  280. 				if(i==t&&e.to==s) {
  281. 					initial=e.flow;
  282. 					continue;
  283. 				}
  284. 				PR1.AddEdge(i,e.to,e.cap-e.flow);
  285. 				PR1.AddEdge(e.to,i,e.flow);
  286. 			}
  287. 		}
  288. 		return initial+PR1.GetMaxFlow(s,t);
  289. 	}
  290. };
  291.  
  292. const int N=30005;
  293. int in[N],ut[N],oin[N],out[N];
  294. pii il[N],ul[N];
  295. pii oil[N],oul[N];
  296. void solve() {
  297. 	int n=readIntSp(1,30000),m=readIntSp(0,30000),q=readIntLn(0,300000);
  298. //	int n,m,q;
  299. //	cin>>n>>m>>q;
  300. 	fr(i,1,n) {
  301. 		oil[i]={0,m};
  302. 		oul[i]={0,m};
  303. 		il[i]={0,m};
  304. 		ul[i]={0,m};
  305. 		in[i]=ut[i]=oin[i]=out[i]=0;
  306. 	}
  307. 	sum_n+=n;
  308. 	sum_m+=m;
  309. 	sum_q+=q;
  310. 	assert(sum_n<=60000&&sum_m<=60000&&sum_q<=600000);
  311. 	SCC G;
  312. 	G.init(n);
  313. 	vector<pii> edg;
  314. 	fr(i,1,m) {
  315. 		int u=readIntSp(1,n),v=readIntLn(1,n);
  316. //		int u,v;
  317. //		cin>>u>>v;
  318. 		assert(u!=v);
  319. 		G.add(u,v);
  320. 		edg.pb({u,v});
  321. 	}
  322. 	G.compute();
  323. 	for(auto e:edg) {
  324. 		out[e.fi]++;
  325. 		oin[e.se]++;
  326. 		ut[G.scc[e.fi]]++;
  327. 		in[G.scc[e.se]]++;
  328. 	}
  329. 	fr(i,1,n) {
  330. 		oil[i].se=oin[i];
  331. 		oul[i].se=out[i];
  332. 		il[i].se=in[i];
  333. 		ul[i].se=ut[i];
  334. 	}
  335. 	int c1=readIntSp(1,1000000000),c2=readIntLn(1,1000000000);
  336. 	bool swapped=0;
  337. 	if(c1>c2) {
  338. 		swapped=1;
  339. 		swap(c1,c2);
  340. 	}
  341. 	int src=2*n+2*G.cnt+1,sink=2*n+2*G.cnt+2;
  342. 	MaxFlowLowerBound F(2*n+2*G.cnt+5,src,sink);
  343. 	bool no=0;
  344. 	fr(i,1,q) {
  345. 		int t=readIntSp(1,4),w=readIntSp(1,n),x=readIntSp(1,2),l=readIntSp(0,m),r=readIntLn(l,m);
  346. 		if(G.scc[w]==1&&t<=2) {
  347. 			trace(t,w,x,l,r,ul[1]);
  348. 		}
  349. 		if(t<=2)
  350. 			w=G.scc[w];
  351. 		if(swapped)
  352. 			x^=3;
  353. 		if(x==2) {
  354. 			int total;
  355. 			if(t==1) {
  356. 				total=ut[w];
  357. 			} else if(t==2) {
  358. 				total=in[w];
  359. 			} else if(t==3) {
  360. 				total=out[w];
  361. 			} else {
  362. 				total=oin[w];
  363. 			}
  364. 			int nl=total-r,nr=total-l;
  365. 			l=nl;
  366. 			r=nr;
  367. 		}
  368. 		if(t==1) {
  369. 			ul[w].fi=max(ul[w].fi,l);
  370. 			ul[w].se=min(ul[w].se,r);
  371. 		} else if(t==2) {
  372. 			il[w].fi=max(il[w].fi,l);
  373. 			il[w].se=min(il[w].se,r);
  374. 		} else if(t==3) {
  375. 			oul[w].fi=max(oul[w].fi,l);
  376. 			oul[w].se=min(oul[w].se,r);
  377. 		} else {
  378. 			oil[w].fi=max(oil[w].fi,l);
  379. 			oil[w].se=min(oil[w].se,r);
  380. 		}
  381. 		if(w==1&&t==1)
  382. 			trace(ul[1],l,r);
  383. 	}
  384. 	fr(i,1,G.cnt)
  385. 		if(ul[i].fi>ul[i].se||il[i].fi>il[i].se) {
  386. 			no=1;
  387. 		}
  388. 	fr(i,1,n)
  389. 		if(oul[i].fi>oul[i].se||oil[i].fi>oil[i].se)
  390. 			no=1;
  391. 	if(no) {
  392. 		cout<<-1<<endl;
  393. 		return;
  394. 	}
  395. 	fr(i,1,G.cnt) {
  396. 		F.AddEdge(src, 2*n+i, ul[i].fi, ul[i].se);
  397. 		F.AddEdge(2*n+G.cnt+i, sink, il[i].fi, il[i].se);
  398. 	}
  399. 	fr(i,1,n) {
  400. 		F.AddEdge(2*n+G.scc[i], i, oul[i].fi, oul[i].se);
  401. 		F.AddEdge(n+i, 2*n+G.cnt+G.scc[i], oil[i].fi, oil[i].se);
  402. 	}
  403. 	for(auto i:edg)
  404. 		F.AddEdge(i.fi, n+i.se, 0, 1);
  405. 	int ans=F.GetMaxFlow();
  406. 	if(~ans)
  407. 		ans=m*c2+(c1-c2)*ans;
  408. 	cout<<ans<<endl;
  409. }
  410.  
  411. signed main() {
  412. 	ios_base::sync_with_stdio(0),cin.tie(0);
  413. 	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
  414. 	cout<<fixed<<setprecision(8);
  415. 	int t=readIntLn(1,100);
  416. 	fr(i,1,t)
  417. 		solve();
  418. 	assert(getchar()==EOF);
  419. 	return 0;
  420. }
  421.  
Runtime error #stdin #stdout #stderr 0s 4292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:81: long long int readInt(long long int, long long int, char): Assertion `false' failed.
https://ideone.com/GDb7oa
language:
C++14 (gcc 8.3)
created:
3 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!