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 * 2; 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(vector<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. vector<int> prod;
  115. vector<int> cost;
  116. void printPath() 
  117. { 
  118.     int i; 
  119.     for (i = 0; i < (int)stacker.size() - 1; 
  120.          i++) { 
  121.         cout << stacker[i] << " -> ";
  122.         prod.push_back(cost[stacker[i]]);
  123.         cout<<prod[i]<<"\n";
  124.     } 
  125.     cout << stacker[i]; 
  126.     prod.push_back(cost[stacker[i]]);
  127. } 
  128.  
  129.  
  130. void DFS(vector<int> v[], 
  131.          bool vis[], 
  132.          int x, 
  133.          int y) 
  134. { 
  135.     stacker.push_back(x); 
  136.     if (x == y) { 
  137.     	printPath();
  138.     	cout<<"\n";
  139.         return; 
  140.     } 
  141.     vis[x] = true; 
  142.     int flag = 0; 
  143.     if (!v[x].empty()) { 
  144.         for (int j = 0; j < v[x].size(); j++) { 
  145.  
  146.             if (vis[v[x][j]] == false) { 
  147.                 DFS(v, vis, v[x][j], y); 
  148.                 flag = 1; 
  149.             } 
  150.         } 
  151.     } 
  152.     if (flag == 0) { 
  153.  
  154.  
  155.         stacker.pop_back(); 
  156.     } 
  157. } 
  158.  
  159. // DFS function for a given vertex x. 
  160. void DFSCall(int x, 
  161.              int y, 
  162.              vector<int> v[], 
  163.              int n 
  164.              ) 
  165. { 
  166.     bool vis[n + 1]; 
  167.  
  168.     memset(vis, false, sizeof(vis)); 
  169.     DFS(v, vis, x, y); 
  170. } 
  171.  
  172. // Driver program to test above functions 
  173. int main() 
  174. { 
  175. 	IOS;
  176.  
  177. 	// array of vectors is used to store the graph 
  178. 	// in the form of an adjacency list 
  179.  
  180. 	sieve();
  181. 	int source,dest; 
  182.  
  183.  
  184. 	int t,n;
  185. 	cin>>t;
  186. 	while(t--)
  187. 	{
  188.  
  189.  
  190. 		cin>>n;
  191. 		int v=n+1;
  192. 		vector<int> adj[v]; 
  193. 		int s,e,k;
  194.  
  195. 		k=n-1;
  196. 		while(k--)
  197. 		{
  198. 			cin>>s>>e;
  199. 			addEdge(adj, s, e); 
  200. 		}
  201. 		k=0;
  202. 		int costp;
  203. 		while(k!=n)
  204. 		{cin>>costp;
  205. 		cost.push_back(costp);
  206. 		k++;}
  207. 		int r;
  208.  
  209. 		cin>>r;
  210. 		while(r--)
  211. 		{
  212.  
  213. 			cin>>source>>dest;
  214. 			DFSCall(source, dest, adj, n+1);
  215. 			int zz=stacker.size();
  216. 			//cout<<"Stack size="<<stacker.size()<<"\n";
  217. 				//map<int, int> Counter;
  218. 				/*int prod[stacker.size()];
  219. 				int zz=stacker.size();
  220. 				int i;*/
  221. 			/*for (i = 0; i<(int)stacker.size()-1; i++)
  222. 			{//prod=prod*cost[path[i]];
  223.  
  224. 			prod[i]=cost[stacker[i]];
  225. 			//cout<<"path "<<i<<":"<<path[i]<<"\n";
  226.  
  227.  
  228.             
  229.                     
  230. 			}
  231. 			prod[i]=cost[dest];*/
  232.  
  233. 			//for(int i=0;i<zz;i++)
  234. 			//cout<<"arr="<<prod[i]<<" ";
  235. 			//cout<<"\n";
  236.  
  237. 			if(source!=dest)
  238. 			cout<<numberOfDivisorsOfProduct(prod,zz)%1000000007<<"\n";
  239. 			else
  240. 			{
  241. 				//prod[0]=cost[dest];
  242. 			cout<<numberOfDivisorsOfProduct(prod,1)%1000000007<<"\n";
  243. 			}
  244. 			stacker.clear();
  245. 			prime_count.clear();
  246. 			prod.clear();
  247. 		}
  248. 		cost.clear();
  249.  
  250. 	}
  251.  
  252.  
  253.  
  254. 	return 0; 
  255. }
Time limit exceeded #stdin #stdout 5s 42520KB
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 
Standard output is empty
https://ideone.com/vgI2AK
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!