fork download
copy 
  1. // BEGIN CUT HERE
  2.  
  3. // END CUT HERE
  4. #line 5 "PublicTransitHard.cpp"
  5. #include <iostream>
  6. #include <sstream>
  7. #include <set>
  8. #include <map>
  9. #include <bitset>
  10. #include <algorithm>
  11. #include <utility>
  12. #include <numeric>
  13. #include <functional>
  14. #include <vector>
  15. #include <queue>
  16. #include <stack>
  17. #include <string>
  18. #include <cstdlib>
  19. #include <cstdio>
  20. #include <cstring>
  21. #include <ctime>
  22. #include <cmath>
  23. #include <cassert>
  24. #include <climits>
  25.  
  26. #define forn(i, n) for (int i = 0; i < int(n); i++)
  27. #define forl(i, n) for (int i = 1; i <= int(n); i++)
  28. #define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
  29. #define fore(i, l, r) for (int i = int(l); i <= int(r); i++)
  30. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  31. #define all(a) (a).begin(), (a).end()
  32. #define sz(a) int((a).size())
  33. #define pb(a) push_back(a)
  34. #define mp(x, y) make_pair((x), (y))
  35. #define ft first
  36. #define sc second
  37. #define x first
  38. #define y second
  39. #define isnan(a) false
  40. #define isinf(a) false
  41.  
  42. using namespace std;
  43.  
  44. typedef long long li;
  45. typedef long double ld;
  46. typedef pair<int, int> pt;
  47.  
  48. template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
  49. template<typename X> inline X sqr(const X& a) { return a * a; }
  50.  
  51. const int INF = int(1e9);
  52. const li INF64 = li(1e18);
  53. const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
  54.  
  55. class PublicTransitHard
  56. {
  57. 	public:
  58. 	int countValidTeleporters(int N, vector <int> edges, int X);
  59. };
  60.  
  61. struct value {
  62. 	pt r[3], d[2];
  63. 	value() {
  64. 		forn(i, 2) r[i] = d[i] = mp(0, -1);
  65. 		r[2] = mp(-1, -1);
  66. 	}
  67. 	void addr(pt rv) {
  68. 		if (r[0] < rv) r[2] = r[1], r[1] = r[0], r[0] = rv;
  69. 		else if (r[1] < rv) r[2] = r[1], r[1] = rv;
  70. 		else if (r[2] < rv) r[2] = rv;
  71. 	}
  72. 	void addd(pt rd) {
  73. 		if (d[0] < rd) d[1] = d[0], d[0] = rd;
  74. 		else if (d[1] < rd) d[1] = rd;
  75. 	}
  76. 	int getr(int i1 = -2, int i2 = -2) {
  77. 		forn(i, 3) if (r[i].y != i1 && r[i].y != i2) return r[i].x;
  78. 		throw;
  79. 	}
  80. 	int getd(int i1 = -2, int i2 = -2) {
  81. 		forn(i, 2) if (d[i].y != i1 && d[i].y != i2) return d[i].x;
  82. 		return 0;
  83. 	}
  84. 	int getdbyr(int i1) {
  85. 		int ans = 0, c = 2;
  86. 		forn(i, 3) if (r[i].y != i1 && c > 0) ans += r[i].x, c--;
  87. 		return ans;
  88. 	}
  89. 	int getid(int val) {
  90. 		forn(i, 3) if (r[i].x == val) return i;
  91. 		throw;
  92. 	}
  93. };
  94.  
  95. const int N = 2000 + 3;
  96.  
  97. int n, x, ans;
  98. vector<int> g[N];
  99. value z[N][N];
  100.  
  101. void solve(int v, int p) {
  102. 	value& ans = z[v][p];
  103. 	if (ans.r[2].x != -1) return;
  104. 	ans.r[2] = mp(0, -1);
  105.  
  106. 	forn(i, sz(g[v])) {
  107. 		int to = g[v][i];
  108. 		if (to == p) continue;
  109. 		solve(to, v);
  110. 		value& next = z[to][v];
  111. 		ans.addd(mp(ans.r[0].x + next.r[0].x + 1, v));
  112. 		ans.addr(mp(next.r[0].x + 1, to));
  113. 		ans.addd(mp(next.d[0].x, to));
  114. 	}
  115. }
  116.  
  117. int w[N][N][3];
  118.  
  119. void dfs1(int rt, int j, int v, int p, int maxl, int d) {
  120. 	int d1 = z[rt][n].r[j].x;
  121. 	int d2 = z[v][p].r[0].x;
  122. 	if (p == n && d1 > x) maxl = -1;
  123.  
  124. 	int cmaxl = maxl;
  125. 	if (p != n && d1 + d2 + d > x) cmaxl = min(cmaxl, x + d - d1 - d2);
  126. 	w[rt][v][j] = cmaxl;
  127.  
  128. 	forn(i, sz(g[v])) {
  129. 		int to = g[v][i];
  130. 		if (to == p) continue;
  131. 		int nmaxl = maxl;
  132. 		d2 = z[v][p].getr(to);
  133. 		if (p != n && d1 + d2 + d > x) nmaxl = min(nmaxl, x + d - d1 - d2);
  134. 		dfs1(rt, j, to, v, nmaxl, d + 1);
  135. 	}
  136. }
  137.  
  138. void dfs2(int rt, int v, int p, int d, int maxd, int maxl) {
  139. 	int j = z[v][n].getid(z[v][n].getr(p));
  140. 	int cmaxl = min(w[v][rt][j], maxl);
  141. 	int cmaxd = max(maxd, z[v][p].d[0].x);
  142. 	if (d <= cmaxl && cmaxd <= x) {
  143. 		ans += 1 + (d == 0);
  144. 	}
  145.  
  146. 	forn(i, sz(g[v])) {
  147. 		int to = g[v][i];
  148. 		if (to == p) continue;
  149. 		int nmaxd = max(maxd, z[v][p].getd(v, to));
  150. 		nmaxd = max(nmaxd, z[v][p].getdbyr(to));
  151. 		j = z[v][n].getid(z[v][to].getr(p));
  152. 		int nmaxl = min(w[v][rt][j], maxl);
  153. 		dfs2(rt, to, v, d + 1, nmaxd, nmaxl);
  154. 	}
  155. }
  156.  
  157. int PublicTransitHard::countValidTeleporters(int _n, vector <int> ed, int _x) {
  158. 	n = _n, x = _x, ans = 0;
  159. 	forn(i, n) g[i].clear();
  160. 	forn(i, sz(ed)) {
  161. 		g[i + 1].pb(ed[i]);
  162. 		g[ed[i]].pb(i + 1);
  163. 	}
  164. 	forn(i, n + 1) forn(j, n + 1) z[i][j] = value();
  165.  
  166. 	forn(i, n) forn(j, sz(g[i])) solve(g[i][j], i);
  167. 	forn(i, n) solve(i, n);
  168.  
  169. 	forn(i, n) forn(j, 3) dfs1(i, j, i, n, n - 1, 0);
  170.  
  171. 	forn(i, n) dfs2(i, i, n, 0, 0, n - 1);
  172.  
  173. 	assert(ans % 2 == 0);
  174. 	ans >>= 1;
  175. 	return ans;
  176. }
  177.  
  178. // BEGIN CUT HERE
  179. namespace moj_harness {
  180. 	int run_test_case(int);
  181. 	void run_test(int casenum = -1, bool quiet = false) {
  182. 		if (casenum != -1) {
  183. 			if (run_test_case(casenum) == -1 && !quiet) {
  184. 				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
  185. 			}
  186. 			return;
  187. 		}
  188.  
  189. 		int correct = 0, total = 0;
  190. 		for (int i=0;; ++i) {
  191. 			int x = run_test_case(i);
  192. 			if (x == -1) {
  193. 				if (i >= 100) break;
  194. 				continue;
  195. 			}
  196. 			correct += x;
  197. 			++total;
  198. 		}
  199.  
  200. 		if (total == 0) {
  201. 			cerr << "No test cases run." << endl;
  202. 		} else if (correct < total) {
  203. 			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
  204. 		} else {
  205. 			cerr << "All " << total << " tests passed!" << endl;
  206. 		}
  207. 	}
  208.  
  209. 	int verify_case(int casenum, const int &expected, const int &received, clock_t elapsed) { 
  210. 		cerr << "Example " << casenum << "... "; 
  211.  
  212. 		string verdict;
  213. 		vector<string> info;
  214. 		char buf[100];
  215.  
  216. 		if (elapsed > CLOCKS_PER_SEC / 200) {
  217. 			sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
  218. 			info.push_back(buf);
  219. 		}
  220.  
  221. 		if (expected == received) {
  222. 			verdict = "PASSED";
  223. 		} else {
  224. 			verdict = "FAILED";
  225. 		}
  226.  
  227. 		cerr << verdict;
  228. 		if (!info.empty()) {
  229. 			cerr << " (";
  230. 			for (int i=0; i<(int)info.size(); ++i) {
  231. 				if (i > 0) cerr << ", ";
  232. 				cerr << info[i];
  233. 			}
  234. 			cerr << ")";
  235. 		}
  236. 		cerr << endl;
  237.  
  238. 		if (verdict == "FAILED") {
  239. 			cerr << "    Expected: " << expected << endl; 
  240. 			cerr << "    Received: " << received << endl; 
  241. 		}
  242.  
  243. 		return verdict == "PASSED";
  244. 	}
  245.  
  246. 	int run_test_case(int casenum) {
  247. 		switch (casenum) {
  248. 		case 0: {
  249. 			int N                     = 4;
  250. 			int edges[]               = {0, 1, 2};
  251. 			int X                     = 1;
  252. 			int expected__            = 1;
  253.  
  254. 			clock_t start__           = clock();
  255. 			int received__            = PublicTransitHard().countValidTeleporters(N, vector <int>(edges, edges + (sizeof edges / sizeof edges[0])), X);
  256. 			return verify_case(casenum, expected__, received__, clock()-start__);
  257. 		}
  258. 		case 1: {
  259. 			int N                     = 3;
  260. 			int edges[]               = {0, 0};
  261. 			int X                     = 2;
  262. 			int expected__            = 6;
  263.  
  264. 			clock_t start__           = clock();
  265. 			int received__            = PublicTransitHard().countValidTeleporters(N, vector <int>(edges, edges + (sizeof edges / sizeof edges[0])), X);
  266. 			return verify_case(casenum, expected__, received__, clock()-start__);
  267. 		}
  268. 		case 2: {
  269. 			int N                     = 6;
  270. 			int edges[]               = {0, 0, 0, 1, 1};
  271. 			int X                     = 2;
  272. 			int expected__            = 1;
  273.  
  274. 			clock_t start__           = clock();
  275. 			int received__            = PublicTransitHard().countValidTeleporters(N, vector <int>(edges, edges + (sizeof edges / sizeof edges[0])), X);
  276. 			return verify_case(casenum, expected__, received__, clock()-start__);
  277. 		}
  278. 		case 3: {
  279. 			int N                     = 7;
  280. 			int edges[]               = {0, 1, 0, 1, 2, 4};
  281. 			int X                     = 3;
  282. 			int expected__            = 0;
  283.  
  284. 			clock_t start__           = clock();
  285. 			int received__            = PublicTransitHard().countValidTeleporters(N, vector <int>(edges, edges + (sizeof edges / sizeof edges[0])), X);
  286. 			return verify_case(casenum, expected__, received__, clock()-start__);
  287. 		}
  288. 		case 4: {
  289. 			int N                     = 16;
  290. 			int edges[]               = {0, 1, 0, 2, 0, 0, 4, 5, 8, 9, 10, 11, 8, 4, 6};
  291. 			int X                     = 7;
  292. 			int expected__            = 31;
  293.  
  294. 			clock_t start__           = clock();
  295. 			int received__            = PublicTransitHard().countValidTeleporters(N, vector <int>(edges, edges + (sizeof edges / sizeof edges[0])), X);
  296. 			return verify_case(casenum, expected__, received__, clock()-start__);
  297. 		}
  298. 		case 5: {
  299. 			int N                     = 56;
  300. 			int edges[]               = {0, 1, 1, 3, 1, 5, 1, 0, 8, 8, 10, 10, 12, 10, 10, 8, 16, 16, 18, 19, 19, 21, 19, 19, 24, 25, 25, 27, 18, 0, 30, 30, 30, 33, 34, 34, 34, 30, 38, 39, 39, 38, 42, 43, 0, 45, 45, 45, 48, 45, 45, 51, 45, 53, 54};
  301. 			int X                     = 12;
  302. 			int expected__            = 610;
  303.  
  304. 			clock_t start__           = clock();
  305. 			int received__            = PublicTransitHard().countValidTeleporters(N, vector <int>(edges, edges + (sizeof edges / sizeof edges[0])), X);
  306. 			return verify_case(casenum, expected__, received__, clock()-start__);
  307. 		}
  308.  
  309. 		// custom cases
  310.  
  311. /*      case 6: {
  312. 			int N                     = ;
  313. 			int edges[]               = ;
  314. 			int X                     = ;
  315. 			int expected__            = ;
  316.  
  317. 			clock_t start__           = clock();
  318. 			int received__            = PublicTransitHard().countValidTeleporters(N, vector <int>(edges, edges + (sizeof edges / sizeof edges[0])), X);
  319. 			return verify_case(casenum, expected__, received__, clock()-start__);
  320. 		}*/
  321. /*      case 7: {
  322. 			int N                     = ;
  323. 			int edges[]               = ;
  324. 			int X                     = ;
  325. 			int expected__            = ;
  326.  
  327. 			clock_t start__           = clock();
  328. 			int received__            = PublicTransitHard().countValidTeleporters(N, vector <int>(edges, edges + (sizeof edges / sizeof edges[0])), X);
  329. 			return verify_case(casenum, expected__, received__, clock()-start__);
  330. 		}*/
  331. /*      case 8: {
  332. 			int N                     = ;
  333. 			int edges[]               = ;
  334. 			int X                     = ;
  335. 			int expected__            = ;
  336.  
  337. 			clock_t start__           = clock();
  338. 			int received__            = PublicTransitHard().countValidTeleporters(N, vector <int>(edges, edges + (sizeof edges / sizeof edges[0])), X);
  339. 			return verify_case(casenum, expected__, received__, clock()-start__);
  340. 		}*/
  341. 		default:
  342. 			return -1;
  343. 		}
  344. 	}
  345. }
  346.  
  347.  
  348. int main(int argc, char *argv[]) {
  349. 	if (argc == 1) {
  350. 		moj_harness::run_test();
  351. 	} else {
  352. 		for (int i=1; i<argc; ++i)
  353. 			moj_harness::run_test(atoi(argv[i]));
  354. 	}
  355. }
  356. // END CUT HERE
  357.  
  358.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:4: error: illegal character: '#'
#line 5 "PublicTransitHard.cpp"
^
Main.java:4: error: class, interface, or enum expected
#line 5 "PublicTransitHard.cpp"
      ^
Main.java:5: error: illegal character: '#'
#include <iostream>
^
Main.java:6: error: illegal character: '#'
#include <sstream>
^
Main.java:7: error: illegal character: '#'
#include <set>
^
Main.java:8: error: illegal character: '#'
#include <map>
^
Main.java:9: error: illegal character: '#'
#include <bitset>
^
Main.java:10: error: illegal character: '#'
#include <algorithm>
^
Main.java:11: error: illegal character: '#'
#include <utility>
^
Main.java:12: error: illegal character: '#'
#include <numeric>
^
Main.java:13: error: illegal character: '#'
#include <functional>
^
Main.java:14: error: illegal character: '#'
#include <vector>
^
Main.java:15: error: illegal character: '#'
#include <queue>
^
Main.java:16: error: illegal character: '#'
#include <stack>
^
Main.java:17: error: illegal character: '#'
#include <string>
^
Main.java:18: error: illegal character: '#'
#include <cstdlib>
^
Main.java:19: error: illegal character: '#'
#include <cstdio>
^
Main.java:20: error: illegal character: '#'
#include <cstring>
^
Main.java:21: error: illegal character: '#'
#include <ctime>
^
Main.java:22: error: illegal character: '#'
#include <cmath>
^
Main.java:23: error: illegal character: '#'
#include <cassert>
^
Main.java:24: error: illegal character: '#'
#include <climits>
^
Main.java:26: error: illegal character: '#'
#define forn(i, n) for (int i = 0; i < int(n); i++)
^
Main.java:26: error: class, interface, or enum expected
#define forn(i, n) for (int i = 0; i < int(n); i++)
                                   ^
Main.java:26: error: class, interface, or enum expected
#define forn(i, n) for (int i = 0; i < int(n); i++)
                                               ^
Main.java:27: error: illegal character: '#'
#define forl(i, n) for (int i = 1; i <= int(n); i++)
^
Main.java:27: error: class, interface, or enum expected
#define forl(i, n) for (int i = 1; i <= int(n); i++)
                                   ^
Main.java:27: error: class, interface, or enum expected
#define forl(i, n) for (int i = 1; i <= int(n); i++)
                                                ^
Main.java:28: error: illegal character: '#'
#define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
^
Main.java:28: error: class, interface, or enum expected
#define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
                                            ^
Main.java:28: error: class, interface, or enum expected
#define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
                                                    ^
Main.java:29: error: illegal character: '#'
#define fore(i, l, r) for (int i = int(l); i <= int(r); i++)
^
Main.java:29: error: class, interface, or enum expected
#define fore(i, l, r) for (int i = int(l); i <= int(r); i++)
                                           ^
Main.java:29: error: class, interface, or enum expected
#define fore(i, l, r) for (int i = int(l); i <= int(r); i++)
                                                        ^
Main.java:30: error: illegal character: '#'
#define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
^
Main.java:31: error: illegal character: '#'
#define all(a) (a).begin(), (a).end()
^
Main.java:32: error: illegal character: '#'
#define sz(a) int((a).size())
^
Main.java:33: error: illegal character: '#'
#define pb(a) push_back(a)
^
Main.java:34: error: illegal character: '#'
#define mp(x, y) make_pair((x), (y))
^
Main.java:35: error: illegal character: '#'
#define ft first
^
Main.java:36: error: illegal character: '#'
#define sc second
^
Main.java:37: error: illegal character: '#'
#define x first
^
Main.java:38: error: illegal character: '#'
#define y second
^
Main.java:39: error: illegal character: '#'
#define isnan(a) false
^
Main.java:40: error: illegal character: '#'
#define isinf(a) false
^
Main.java:44: error: class, interface, or enum expected
typedef long long li;
^
Main.java:45: error: class, interface, or enum expected
typedef long double ld;
^
Main.java:46: error: class, interface, or enum expected
typedef pair<int, int> pt;
^
Main.java:48: error: class, interface, or enum expected
template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
^
Main.java:48: error: class, interface, or enum expected
template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
                                                                     ^
Main.java:49: error: class, interface, or enum expected
template<typename X> inline X sqr(const X& a) { return a * a; }
                                                              ^
Main.java:52: error: class, interface, or enum expected
const li INF64 = li(1e18);
^
Main.java:53: error: class, interface, or enum expected
const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
^
Main.java:57: error: illegal start of type
	public:
	      ^
Main.java:57: error: ';' expected
	public:
	       ^
Main.java:58: error: invalid method declaration; return type required
	int countValidTeleporters(int N, vector <int> edges, int X);
	    ^
Main.java:61: error: class, interface, or enum expected
struct value {
^
Main.java:63: error: class, interface, or enum expected
	value() {
	^
Main.java:65: error: class, interface, or enum expected
		r[2] = mp(-1, -1);
		^
Main.java:66: error: class, interface, or enum expected
	}
	^
Main.java:69: error: class, interface, or enum expected
		else if (r[1] < rv) r[2] = r[1], r[1] = rv;
		^
Main.java:70: error: class, interface, or enum expected
		else if (r[2] < rv) r[2] = rv;
		^
Main.java:71: error: class, interface, or enum expected
	}
	^
Main.java:74: error: class, interface, or enum expected
		else if (d[1] < rd) d[1] = rd;
		^
Main.java:75: error: class, interface, or enum expected
	}
	^
Main.java:78: error: class, interface, or enum expected
		throw;
		^
Main.java:79: error: class, interface, or enum expected
	}
	^
Main.java:82: error: class, interface, or enum expected
		return 0;
		^
Main.java:83: error: class, interface, or enum expected
	}
	^
Main.java:86: error: class, interface, or enum expected
		forn(i, 3) if (r[i].y != i1 && c > 0) ans += r[i].x, c--;
		^
Main.java:87: error: class, interface, or enum expected
		return ans;
		^
Main.java:88: error: class, interface, or enum expected
	}
	^
Main.java:91: error: class, interface, or enum expected
		throw;
		^
Main.java:92: error: class, interface, or enum expected
	}
	^
Main.java:95: error: class, interface, or enum expected
const int N = 2000 + 3;
^
Main.java:97: error: class, interface, or enum expected
int n, x, ans;
^
Main.java:98: error: class, interface, or enum expected
vector<int> g[N];
^
Main.java:99: error: class, interface, or enum expected
value z[N][N];
^
Main.java:101: error: class, interface, or enum expected
void solve(int v, int p) {
^
Main.java:103: error: class, interface, or enum expected
	if (ans.r[2].x != -1) return;
	^
Main.java:104: error: class, interface, or enum expected
	ans.r[2] = mp(0, -1);
	^
Main.java:106: error: class, interface, or enum expected
	forn(i, sz(g[v])) {
	^
Main.java:108: error: class, interface, or enum expected
		if (to == p) continue;
		^
Main.java:109: error: class, interface, or enum expected
		solve(to, v);
		^
Main.java:110: error: class, interface, or enum expected
		value& next = z[to][v];
		^
Main.java:111: error: class, interface, or enum expected
		ans.addd(mp(ans.r[0].x + next.r[0].x + 1, v));
		^
Main.java:112: error: class, interface, or enum expected
		ans.addr(mp(next.r[0].x + 1, to));
		^
Main.java:113: error: class, interface, or enum expected
		ans.addd(mp(next.d[0].x, to));
		^
Main.java:114: error: class, interface, or enum expected
	}
	^
Main.java:119: error: class, interface, or enum expected
void dfs1(int rt, int j, int v, int p, int maxl, int d) {
^
Main.java:121: error: class, interface, or enum expected
	int d2 = z[v][p].r[0].x;
	^
Main.java:122: error: class, interface, or enum expected
	if (p == n && d1 > x) maxl = -1;
	^
Main.java:124: error: class, interface, or enum expected
	int cmaxl = maxl;
	^
Main.java:125: error: class, interface, or enum expected
	if (p != n && d1 + d2 + d > x) cmaxl = min(cmaxl, x + d - d1 - d2);
	^
Main.java:126: error: class, interface, or enum expected
	w[rt][v][j] = cmaxl;
	^
Main.java:128: error: class, interface, or enum expected
	forn(i, sz(g[v])) {
	^
Main.java:130: error: class, interface, or enum expected
		if (to == p) continue;
		^
Main.java:131: error: class, interface, or enum expected
		int nmaxl = maxl;
		^
Main.java:132: error: class, interface, or enum expected
		d2 = z[v][p].getr(to);
		^
Main.java:133: error: class, interface, or enum expected
		if (p != n && d1 + d2 + d > x) nmaxl = min(nmaxl, x + d - d1 - d2);
		^
100 errors
stdout
copy 
Standard output is empty
https://ideone.com/xp8nrx
language:
Java (HotSpot 12)
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!