fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. #include <iostream>
  4. #include <string>
  5. #include <cstdlib> 
  6. #include <string.h>
  7. #include <vector>
  8. #include <cstdio>
  9. #include <iomanip>
  10. #include <stack>
  11. #include <set>
  12. #include <map>
  13. #include <list>
  14. #include <ctime>
  15. #include <algorithm>
  16. #include <cmath>
  17. #define PI 3.1415926535897932384626433832795l
  18. #define IOS ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0)
  19. #define deci(n) cout<<fixed<<setprecision(n);
  20. #define F first
  21. #define S second
  22. #define mk make_pair
  23. #define pb push_back
  24. #define ALPHA 27
  25. #define ll long long int
  26. #define ld long double
  27. #define mmset(arr, n) memset(arr, n, sizeof arr)
  28. #define debug(x) cerr << '#' << ' ' << x << '\n'
  29. #define len(s) s.length()
  30. #define ForA(i,a,b) for(int i = a; i < b; i++)
  31. #define ForA1(i,a,b) for(int i = b - 1; i >= a; i--)
  32. #define ForB1(i,a,b) for(int i = b; i > a; i--)
  33. #define ForB(i,a,b) for(int i = a; i <= b; i++)
  34. #define INT_SIZE 18 
  35. #define maxn 100010
  36.  
  37. using namespace std;
  38. #define MAX 10000002 
  39. const ll INF = (ll)(8e18);
  40. const ll MOD = 1000000007;
  41. const ll Maxn = 1000000000000;
  42.  
  43. ll F[maxn], Ans[maxn];
  44. vector<int> stacker;
  45. int total = 0, N = 0, Number;
  46.  
  47. int prime[MAX];
  48.  
  49. unordered_map<int, int> prime_count; 
  50.  
  51. // Function to store smallest prime factor 
  52. // in prime[] 
  53. void sieve() 
  54. { 
  55. 	memset(prime, 0, sizeof(prime)); 
  56. 	prime[0] = prime[1] = 1; 
  57. 	for (int i = 2; i * i < MAX; i++) { 
  58. 		if (prime[i] == 0) { 
  59. 			for (int j = i * i; j < MAX; j += i) { 
  60. 				if (prime[j] == 0) 
  61. 					prime[j] = i; 
  62. 			} 
  63. 		} 
  64. 	} 
  65. 	for (int i = 2; i < MAX; i++) { 
  66.  
  67. 		// If the number is prime then 
  68. 		// it's the smallest prime factor 
  69. 		// is the number itself 
  70. 		if (prime[i] == 0) 
  71. 			prime[i] = i; 
  72. 	} 
  73. } 
  74.  
  75. // Function to return the count of the divisors for 
  76. // the product of all the numbers from the array 
  77. long long numberOfDivisorsOfProduct(const int* arr, 
  78. 											int n) 
  79. { 
  80.  
  81. 	for (int i = 0; i < n; i++) { 
  82. 		int temp = arr[i]; 
  83. 		while (temp != 1) { 
  84.  
  85. 			// Increase the count of prime 
  86. 			// encountered 
  87. 			prime_count[prime[temp]]++; 
  88. 			temp = temp / prime[temp]; 
  89. 		} 
  90. 	} 
  91.  
  92. 	long long ans = 1; 
  93.  
  94. 	// Multiplying the count of primes 
  95. 	// encountered 
  96. 	unordered_map<int, int>::iterator it; 
  97. 	for (it = prime_count.begin(); 
  98. 		it != prime_count.end(); it++) { 
  99. 		ans = ans * (it->second + 1); 
  100. 	} 
  101.  
  102. 	return ans; 
  103. } 
  104.  
  105.  
  106. void addEdge(vector<int> v[], 
  107.              int x, 
  108.              int y) 
  109. { 
  110.     v[x].push_back(y); 
  111.     v[y].push_back(x); 
  112. } 
  113.  
  114.  
  115. void printPath() 
  116. { 
  117.     int i; 
  118.     for (i = 0; i < (int)stacker.size() - 1; 
  119.          i++) { 
  120.         cout << stacker[i] << " -> "; 
  121.     } 
  122.     cout << stacker[i]; 
  123. } 
  124.  
  125.  
  126. void DFS(vector<int> v[], 
  127.          bool vis[], 
  128.          int x, 
  129.          int y) 
  130. { 
  131. 	cout<<"Pushed:"<<x<<"\n";
  132.     stacker.push_back(x); 
  133.     if (x == y) { 
  134.     	cout<<"x="<<x<<","<<"y="<<y<<"\n";
  135.         return; 
  136.     } 
  137.     vis[x] = true; 
  138.     int flag = 0; 
  139.     if (!v[x].empty()) { 
  140.         for (int j = 0; j < v[x].size(); j++) { 
  141.  
  142.             if (vis[v[x][j]] == false) { 
  143.                 DFS(v, vis, v[x][j], y); 
  144.                 flag = 1; 
  145.             } 
  146.         } 
  147.     } 
  148.     if (flag == 0) { 
  149.  
  150.  
  151.         stacker.pop_back(); 
  152.     } 
  153. } 
  154.  
  155. // DFS function for a given vertex x. 
  156. void DFSCall(int x, 
  157.              int y, 
  158.              vector<int> v[], 
  159.              int n 
  160.              ) 
  161. { 
  162.     bool vis[n + 1]; 
  163.  
  164.     memset(vis, false, sizeof(vis)); 
  165.     DFS(v, vis, x, y); 
  166. } 
  167.  
  168. // Driver program to test above functions 
  169. int main() 
  170. { 
  171. 	IOS;
  172.  
  173. 	// array of vectors is used to store the graph 
  174. 	// in the form of an adjacency list 
  175.  
  176. 	sieve();
  177. 	int source,dest; 
  178.  
  179.  
  180. 	int t,n;
  181. 	cin>>t;
  182. 	while(t--)
  183. 	{
  184.  
  185.  
  186. 		cin>>n;
  187. 		int v=n+1;
  188. 		vector<int> adj[v]; 
  189. 		int s,e,k;
  190. 		int cost[n+1];
  191. 		k=n-1;
  192. 		while(k--)
  193. 		{
  194. 			cin>>s>>e;
  195. 			addEdge(adj, s, e); 
  196. 		}
  197. 		k=0;
  198. 		while(k!=n)
  199. 		{cin>>cost[k+1];
  200. 		k++;}
  201. 		int r;
  202.  
  203. 		cin>>r;
  204. 		while(r--)
  205. 		{
  206.  
  207. 			cin>>source>>dest;
  208. 			DFSCall(source, dest, adj, n+1);
  209. 			cout<<"size="<<stacker.size()<<"\n";
  210. 			//cout<<"Stack size="<<stacker.size()<<"\n";
  211. 				//map<int, int> Counter;
  212. 				int prod[stacker.size()];
  213. 				int zz=stacker.size();
  214. 			for (int i = 0; i <stacker.size(); i++)
  215. 			{//prod=prod*cost[path[i]];
  216.  
  217. 			prod[i]=cost[stacker[i]];
  218. 			//cout<<"path "<<i<<":"<<path[i]<<"\n";
  219. 			cout<<"stacker="<<stacker[i]<<"\n";
  220.  
  221.  
  222.  
  223. 			}
  224.  
  225. 			//for(int i=0;i<zz;i++)
  226. 			//cout<<"arr="<<prod[i]<<" ";
  227. 			//cout<<"\n";
  228.  
  229. 			if(source!=dest)
  230. 			cout<<numberOfDivisorsOfProduct(prod,zz)%1000000007<<"\n";
  231. 			else
  232. 			{
  233. 				//prod[0]=cost[dest];
  234. 			cout<<numberOfDivisorsOfProduct(prod,1)%1000000007<<"\n";
  235. 			}
  236. 			stacker.clear();
  237. 			prime_count.clear();
  238. 		}
  239.  
  240. 	}
  241.  
  242.  
  243.  
  244. 	return 0; 
  245. }
Success #stdin #stdout 0.13s 42680KB
comments (?)
stdin
copy 
1
10
1 2
1 3
3 4
4 5
5 6
2 7
6 8
8 10
7 9
2 6 7 8 4 2 1 9 10 12
5
1 2
2 1
3 1
1 8
8 7
stdout
copy 
Pushed:1
Pushed:2
x=2,y=2
Pushed:3
Pushed:4
Pushed:5
Pushed:6
Pushed:8
Pushed:10
size=7
stacker=1
stacker=2
stacker=3
stacker=4
stacker=5
stacker=6
stacker=8
72
Pushed:2
Pushed:1
x=1,y=1
Pushed:7
Pushed:9
size=3
stacker=2
stacker=1
stacker=7
6
Pushed:3
Pushed:1
x=1,y=1
Pushed:4
Pushed:5
Pushed:6
Pushed:8
Pushed:10
size=6
stacker=3
stacker=1
stacker=4
stacker=5
stacker=6
stacker=8
48
Pushed:1
Pushed:2
Pushed:7
Pushed:9
Pushed:3
Pushed:4
Pushed:5
Pushed:6
Pushed:8
x=8,y=8
size=8
stacker=1
stacker=2
stacker=7
stacker=3
stacker=4
stacker=5
stacker=6
stacker=8
72
Pushed:8
Pushed:6
Pushed:5
Pushed:4
Pushed:3
Pushed:1
Pushed:2
Pushed:7
x=7,y=7
Pushed:10
size=8
stacker=8
stacker=6
stacker=5
stacker=4
stacker=3
stacker=1
stacker=2
stacker=7
72
https://ideone.com/mmhe0z
language:
C++14 (gcc 8.3)
created:
4 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!