fork(1) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <cassert>
  5. #include <cstdlib>
  6. using namespace std;
  7.  
  8. typedef long long int lli;
  9.  
  10. vector<lli> comp, res;
  11. vector<pair<lli, lli>> Q;
  12. vector<vector<pair<lli, lli>>> graph;
  13.  
  14. void dfs(lli node, lli v, lli col)
  15. {
  16. 	comp[node] = v;
  17. 	for(auto it: graph[node])
  18. 	{
  19. 		if(it.second != col && comp[it.first] == -1) dfs(it.first, v, col); 
  20. 	}
  21. }
  22.  
  23. int main(void)
  24. {
  25. 	lli n, m, c, q, u, v, a, x, y;
  26. 	scanf("%lld%lld%lld", &n, &m, &c);
  27. 	graph.clear(); graph.resize(n);
  28. 	for(lli i = 0;i < m;i++)
  29. 	{
  30. 		scanf("%lld%lld%lld", &u, &v, &a);
  31. 		u--; v--;
  32. 		assert(u < n); assert(v < n); assert(a <= c);
  33. 		graph[u].push_back({v, a});
  34. 		graph[v].push_back({u, a});
  35. 		assert(u != v);
  36. 	}
  37.  
  38. 	scanf("%lld", &q);
  39. 	res.clear(); res.resize(q);
  40. 	Q.clear(); Q.resize(q);
  41. 	for(lli i = 0;i < q;i++)
  42. 	{
  43. 		scanf("%lld%lld", &x, &y);
  44. 		x--; y--;
  45. 		Q[i] = {x, y};
  46. 		assert(x != y);
  47. 	}
  48. 	comp.clear(); comp.resize(n, -1);
  49. 	int ctr = 0;
  50. 	for(int i = 0;i < n;i++)
  51. 	{
  52. 		if(comp[i] == -1) dfs(i, ctr++, -1);
  53. 	}
  54. 	vector<lli> pika = comp;
  55.  
  56. 	for(lli i = 1;i <= c;i++)
  57. 	{
  58. 		//cout << i << ": ";
  59. 		lli ctr = 0;
  60. 		comp.clear(); comp.resize(n, -1);
  61. 		for(lli j = 0;j < n;j++)
  62. 		{
  63. 			if(comp[j] == -1) dfs(j, ctr++, i);
  64. 		}
  65.  
  66. 		for(lli j = 0;j < q;j++)
  67. 		{
  68. 			if(comp[Q[j].first] != comp[Q[j].second] || pika[Q[j].first] != pika[Q[j].second])
  69. 			{
  70. 				//cout << j << " ";
  71. 				res[j]++;
  72. 			}
  73. 		}
  74. 		//cout << "\n";
  75. 	}
  76.  
  77. 	for(lli i = 0;i < q;i++) printf("%lld\n", res[i]);
  78. }
Runtime error #stdin #stdout #stderr 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::length_error'
  what():  vector::_M_default_append
https://ideone.com/vrz32D
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!