fork download 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <map>
  4. #include <string>
  5. #include <cstring>
  6. using namespace std;
  7. const int maxc = 100;
  8. const int maxt = 1000;
  9. int c,t,head[maxc+1],link[maxc*maxt+1],adj1[maxc*maxt+1],adj2[maxc*maxt+1],adj3[maxc*maxt+1],tim,s,f,dp[maxc+1][2400+1];
  10. string ss,ff;
  11. map <string,int> m;
  12. void enter()
  13. {
  14. 	memset(head,0,sizeof(head));
  15. 	m.clear();
  16. 	cin >> c;
  17. 	for (int i=1; i<=c; i++)
  18. 	{
  19. 		string s1;
  20. 		cin >> s1;
  21. 		m[s1]=i;
  22. 	}
  23. 	cin >> t;
  24. 	int socanh=0;
  25. 	for (int i=1; i<=t; i++)
  26. 	{
  27. 		int ti;
  28. 		cin >> ti;
  29. 		//cout << ti << '\n';
  30. 		int cs,pre;
  31. 		for (int j=1; j<=ti; j++)
  32. 		{
  33. 			string s1,s2;
  34. 			cin >> s1 >> s2;
  35. 			while ((s1[0]=='0') and (s1.size()>1)) s1.erase(0,1);
  36. 			if (j==1)
  37. 			{
  38. 				cs=m[s2];
  39. 				pre=stoi(s1);
  40. 			}
  41. 			else
  42. 			{
  43. 				int cs2=m[s2];
  44. 				int pre2=stoi(s1);
  45. 				socanh++;
  46. 				link[socanh]=head[cs2];
  47. 				adj1[socanh]=cs;
  48. 				adj2[socanh]=pre2;
  49. 				adj3[socanh]=pre;
  50. 				head[cs2]=socanh;
  51. 				pre=pre2;
  52. 				cs=cs2;
  53. 			}
  54. 		}
  55. 	}
  56. 	string s1,s2;
  57. 	cin >> s1;
  58. 	while ((s1[0]=='0') and (s1.size()>1)) s1.erase(0,1);
  59. 	tim=stoi(s1);
  60. 	cin >> s1 >> s2;
  61. 	s=m[s1];
  62. 	f=m[s2];
  63. 	ss=s1;
  64. 	ff=s2;
  65. 	//cout << s << ' ' << f << '\n';
  66. 	//for (int i=1; i<=c; i++)
  67. 	//	cout << head[i] << ' ' << adj1[head[i]] << '\n';
  68. }
  69. int caldp(int x, int y)
  70. {
  71. 	//cout << x << ' ' << y << '\n';
  72. 	if (dp[x][y]==-2)
  73. 	{
  74. 		if (x==s) dp[x][y]=y;
  75. 		else
  76. 		{
  77. 			dp[x][y]=-1;
  78. 			int i=head[x];
  79. 			//cout << i << '\n';
  80. 			while (i!=0)
  81. 			{
  82. 				if (adj2[i]<=y) dp[x][y]=max(dp[x][y],caldp(adj1[i],adj3[i]));
  83. 				i=link[i];
  84. 			}
  85. 		}
  86. 	}
  87. 	//cout << x << ' ' << y << ' ' << dp[x][y] << '\n';
  88. 	return dp[x][y];
  89. }
  90. void solve()
  91. {
  92. 	for (int i=1; i<=c; i++)
  93. 		for (int j=1; j<=2400; j++)
  94. 			dp[i][j]=-2;
  95. 	//cout << dp[f][1411] << '\n';
  96. 	//cout << "I'm here\n";
  97. 	int mt;
  98. 	for (mt=0; mt<=2400; mt++)
  99. 		if ((caldp(f,mt)>=0) and (caldp(f,mt)>=tim)) break;
  100. 	if ((mt==2400) or (caldp(f,mt)<tim)) cout << "No connection\n";
  101. 	else
  102. 	{
  103. 		string p=to_string(caldp(f,mt));
  104. 		while (p.size()<4) p='0'+p;
  105. 		cout << "Departure " << p << ' ' << ss << '\n';
  106. 		p=to_string(mt);
  107. 		while (p.size()<4) p='0'+p;
  108. 		cout << "Arrival   " << p << ' ' << ff << '\n';
  109. 	}
  110. }
  111. int main()
  112. {
  113. 	ios_base::sync_with_stdio(0);
  114. 	//freopen("10039.inp","r",stdin);
  115. 	//freopen("10039.out","w",stdout);
  116. 	int t;
  117. 	cin >> t;
  118. 	int i=0;
  119. 	for (int i=1; i<=t; i++)
  120. 	{
  121. 		cout << "Scenario " << i << '\n';
  122. 		enter();
  123. 		solve();
  124. 		cout << '\n';
  125. 	}
  126. 	return 0;
  127. }
Runtime error #stdin #stdout #stderr 0s 5968KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::invalid_argument'
  what():  stoi
https://ideone.com/whbn8e
language:
C++14 (gcc 8.3)
created:
8 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!