Advertisement
Josif_tepe

Untitled

Jun 1st, 2022
855
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. //#include <bits/stdc++.h>
  3. #include <stack>
  4. #include <vector>
  5. #include <cstring>
  6. #include <iostream>
  7. using namespace std;
  8. vector<int>graph[500000];
  9. vector<int>vsuma[100005];
  10. int niza[100005];
  11. int najmal=2e9;
  12. vector<int>rev_graph[500000];
  13. int suma[100005];
  14. bool visited[500000];
  15. int brojac1=0;
  16. stack<int>s;
  17.  
  18. void dfs(int node){
  19. visited[node]=true;
  20. for(int i=0; i<graph[node].size(); i++){
  21.     int sosed=graph[node][i];
  22.     if(!visited[sosed]){
  23.         dfs(sosed);
  24.     }
  25. }
  26. s.push(node);
  27. }
  28. void rev_dfs(int node){
  29. visited[node]=true;
  30. if(suma[node]<najmal){
  31.     najmal=suma[node];
  32. }
  33. ////cout<<node<<" ";
  34. for(int i=0; i<rev_graph[node].size(); i++){
  35.     int rev_sosed=rev_graph[node][i];
  36.     if(!visited[rev_sosed]){
  37.         rev_dfs(rev_sosed);
  38.     }
  39. }
  40. }
  41. bool visited2[500005];
  42. void rev_dfs1(int node){
  43.     visited2[node] = true;
  44.     if(suma[node]==najmal){
  45.        
  46.     brojac1+=1;
  47.     }
  48. //    cout << najmal << " " << node + 1 << endl;
  49. for(int i=0; i<rev_graph[node].size(); i++){
  50.     int sosed=rev_graph[node][i];
  51.     if(!visited2[sosed])
  52.         rev_dfs1(sosed);
  53. }
  54. }
  55. int main()
  56. {
  57. int a, b;
  58. long long brojac=0;
  59. cin>>a;
  60. vector<int>v;
  61. for(int i=0; i<a; i++){
  62.     cin>>suma[i];
  63. }
  64.  
  65. cin>>b;
  66. memset(visited, false, sizeof visited);
  67. for(int i=0; i<b; i++){
  68.     int k, k1;
  69.     cin>>k>>k1;
  70.     k1--;
  71.     k--;
  72.     graph[k].push_back(k1);
  73.     rev_graph[k1].push_back(k);
  74. }
  75. for(int i=0; i<a; i++){
  76.     if(!visited[i]){
  77.         dfs(i);
  78.     }
  79. }
  80.     memset(visited2, false, sizeof visited2);
  81. memset(visited, false, sizeof visited);
  82. while(!s.empty()){
  83.     int node=s.top();
  84.         if(!visited[node]){
  85.             najmal = 2e9;
  86.             brojac1 = 0;
  87.             rev_dfs(node);
  88.             brojac+=najmal;
  89.            
  90.             rev_dfs1(node);
  91.             v.push_back(brojac1);
  92.            
  93. }
  94. s.pop();
  95. }
  96. //cout<<brojac<<" ";
  97. long long brojac2=1;
  98.     long long MOD = 1e9 + 7;
  99. for(int i=0; i<v.size(); i++){
  100. //    cout<<v[i]<<endl;
  101.     brojac2*=v[i];
  102.     brojac2 %= MOD;
  103. }
  104.     cout<<brojac << " " << brojac2 << endl;;
  105. return 0;
  106. }
  107.  
Advertisement
RAW Paste Data Copied
Advertisement