fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. typedef long long ll; 
  4.  
  5. using namespace std;
  6. int n;
  7. vector<vector<int>>adj;
  8. int id = 1;
  9. int scc = 0;
  10. vector<int>node_id;
  11. vector<bool>instack;
  12. stack<int>stk;
  13. vector<bool>vis;
  14. vector<int>low_link;
  15. vector<int>kindom;
  16.  
  17. void dfs(int node){
  18. 	vis[node] = 1;
  19. 	instack[node] = 1;
  20. 	stk.push(node);
  21. 	node_id[node] = id++;
  22. 	low_link[node] = node_id[node];
  23.  
  24. 	for(auto x:adj[node]){
  25. 		if(!vis[x]) dfs(x);
  26. 		if(instack[x]) low_link[node] = min(low_link[node], low_link[x]);
  27. 	}
  28. 	if(low_link[node] == node_id[node]){
  29. 		while(!stk.empty()){
  30. 			int x = stk.top(); 
  31. 			stk.pop();
  32. 			instack[x] = 0;
  33. 			low_link[x] = low_link[node];
  34. 			kindom[x] = (scc + 1);
  35. 			if(x == node) break;
  36.  
  37. 		}
  38. 		scc++;
  39. 	}
  40. }
  41. void tarjan(){
  42. 	for(int i = 1;i<=n;i++){
  43. 		if(!vis[i]) dfs(i);
  44. 	}
  45. }
  46.  
  47. ll M = 1e9 + 7; 
  48. int main() {
  49. 	ios_base::sync_with_stdio(false);
  50. 	cin.tie(NULL); cout.tie(NULL);
  51.  
  52. 	cin>>n;
  53.     vector<ll>cost(n + 1); 
  54.     for(int i = 1; i<=n;i++) cin>>cost[i]; 
  55. 	adj.resize(n + 1);
  56. 	int m; cin>>m;
  57. 	for(int i = 0;i<m;i++){
  58. 		int u,v; cin>>u>>v; adj[u].push_back(v);
  59. 	}
  60. 	vis.resize(n + 1,0);
  61. 	low_link.resize(n + 1);
  62. 	iota(low_link.begin(), low_link.end(),0);
  63. 	instack.resize(n + 1,0);
  64. 	node_id.resize(n + 1,0);
  65. 	kindom.resize(n + 1);
  66. 	tarjan();
  67. 	vector<ll> freq(scc + 1,0ll); 
  68.     vector<ll> mn(scc + 1, 2e9 + 1ll); 
  69.     for(int i = 1; i <=n ; i++){
  70.        mn[kindom[i]] = min(mn[kindom[i]], cost[i]); 
  71.     }
  72.     ll sum = 0ll; 
  73.     for(int i = 1; i <= scc ; i++) sum += mn[i]; 
  74.     for(int i = 1; i <= n; i++){
  75.        if(cost[i] == mn[kindom[i]]) freq[kindom[i]]++; 
  76.     }
  77.     ll count = 1ll; 
  78.     for(int i = 1; i <= scc; i++) 
  79.         count = (count*freq[i])%M; 
  80.  
  81. 	cout<<sum<<" "<<count<<'\n';
  82. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3
1 2 3
3
1 2
2 3
3 2
stdout
copy 
3 1
https://ideone.com/mfgPyt
language:
C++ (gcc 8.3)
created:
1 day 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!