fork(1) download 
  1. #include <bits/stdc++.h>
  2. // iostream is too mainstream
  3. #include <cstdio>
  4. // bitch please
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <cstdlib>
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11. #include <queue>
  12. #include <stack>
  13. #include <list>
  14. #include <cmath>
  15. #include <iomanip>
  16. #include <time.h>
  17. #define dibs reserve
  18. #define OVER9000 1234567890123456789LL
  19. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  20. #define tisic 47
  21. #define soclose 1e-8
  22. #define chocolate win
  23. // so much chocolate
  24. #define patkan 9
  25. #define ff first
  26. #define ss second
  27. #define abs(x) ((x < 0)?-(x):x)
  28. #define uint unsigned int
  29. #define dbl long double
  30. #define pi 3.14159265358979323846
  31. using namespace std;
  32. // mylittledoge
  33.  
  34. typedef long long cat;
  35.  
  36. #ifdef DONLINE_JUDGE
  37. 	// palindromic tree is better than splay tree!
  38. 	#define lld I64d
  39. #endif
  40.  
  41. pair<cat,cat> dist(int u, int v, vector<cat> &S) {
  42. 	if(u > v) swap(u,v);
  43. 	return make_pair(S[v]-S[u], S[S.size()-1]-S[v]+S[u]);
  44. }
  45.  
  46. cat minp(pair<cat,cat> p) {
  47. 	return min(p.ff,p.ss);
  48. }
  49.  
  50. int main() {
  51. 	cin.sync_with_stdio(0);
  52. 	cin.tie(0);
  53. 	cout << fixed << setprecision(10);
  54. 	int T;
  55. 	cin >> T;
  56. 	while(T--) {
  57. 		int N,Q;
  58. 		cin >> N >> Q;
  59. 		vector<int> A(N);
  60. 		vector< vector<cat> > cycw(N);
  61. 		for(int i =0; i < N; i++) {
  62. 			cin >> A[i];
  63. 			cycw[i].resize(A[i]);
  64. 			for(int j =0; j < A[i]; j++) cin >> cycw[i][j];
  65. 		}
  66. 		vector<cat> w(N), v1(N), v2(N);
  67. 		for(int i =0; i < N; i++) {
  68. 			cin >> v1[i] >> v2[(i+1)%N] >> w[i];
  69. 			v1[i]--, v2[(i+1)%N]--;
  70. 		}
  71.  
  72. 		// prefix sums in outer cycle
  73. 		vector<cat> W(N+1,0);
  74. 		for(int i =0; i < N; i++) W[i+1] =W[i]+w[i];
  75. 		// prefix sums in inner cycles
  76. 		vector< vector<cat> > cycW(N);
  77. 		for(int i =0; i < N; i++) {
  78. 			cycW[i].resize(A[i]+1,0);
  79. 			for(int j =0; j < A[i]; j++) cycW[i][j+1] =cycW[i][j]+cycw[i][j];
  80. 		}
  81. 		// compute X[i] + prefix sums
  82. 		vector<cat> X(N), S(N+1,0);
  83. 		for(int i =0; i < N; i++) X[i] =minp(dist(v1[i],v2[i],cycW[i]));
  84. 		for(int i =0; i < N; i++) S[i+1] =S[i]+X[i];
  85.  
  86. 		// queries
  87. 		for(int q =0; q < Q; q++) {
  88. 			int u1,c1,u2,c2;
  89. 			cin >> u1 >> c1 >> u2 >> c2;
  90. 			u1--, c1--, u2--, c2--;
  91. 			if(c1 > c2) {
  92. 				swap(c1,c2);
  93. 				swap(u1,u2);
  94. 			}
  95. 			pair<cat,cat> ans =dist(c1,c2,W); // dist. in outer cycle
  96. 			// add dist. from u1, u2 in inner cycles
  97. 			ans.ff +=minp(dist(u1,v1[c1],cycW[c1])) + minp(dist(u2,v2[c2],cycW[c2]));
  98. 			ans.ss +=minp(dist(u1,v2[c1],cycW[c1])) + minp(dist(u2,v1[c2],cycW[c2]));
  99. 			// add dist. v1--v2 in inner cycles
  100. 			ans.ff +=S[c2]-S[c1+1];
  101. 			ans.ss +=S[N]-S[c2+1]+S[c1];
  102. 			cout << minp(ans) << "\n";
  103. 		}
  104. 	}
  105. }
  106.  
  107. // look at my code
  108. // my code is amazing
  109.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/yVh6bO
Codechef October Challenge 2017, CHEFCCYL
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!