fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const ll MOD = 1000000007;
  5.  
  6. int main(){
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int n;
  11.     cin >> n;
  12.     vector<ll> cost(n);
  13.     for(int i = 0; i < n; i++){
  14.         cin >> cost[i];
  15.     }
  16.  
  17.     int m;
  18.     cin >> m;
  19.     vector<vector<int>> adj(n);
  20.     for(int i = 0; i < m; i++){
  21.         int u, v;
  22.         cin >> u >> v;
  23.         --u; --v;               // convert to 0-based
  24.         adj[u].push_back(v);
  25.     }
  26.  
  27.     // Tarjan’s SCC globals
  28.     vector<int> disc(n, -1), low(n, 0);
  29.     vector<bool> onstack(n, false);
  30.     stack<int> st;
  31.     int timer = 0;
  32.     vector<vector<int>> sccs;
  33.  
  34.     // Tarjan’s DFS (recursive)
  35.     function<void(int)> dfs = [&](int u) {
  36.         disc[u] = low[u] = timer++;
  37.         st.push(u);
  38.         onstack[u] = true;
  39.  
  40.         for(int v : adj[u]){
  41.             if(disc[v] == -1) {
  42.                 dfs(v);
  43.                 low[u] = min(low[u], low[v]);
  44.             }
  45.             else if(onstack[v]) {
  46.                 low[u] = min(low[u], disc[v]);
  47.             }
  48.         }
  49.  
  50.         // If u is root of an SCC, pop until u
  51.         if(low[u] == disc[u]) {
  52.             vector<int> comp;
  53.             while(true) {
  54.                 int v = st.top(); st.pop();
  55.                 onstack[v] = false;
  56.                 comp.push_back(v);
  57.                 if(v == u) break;
  58.             }
  59.             sccs.push_back(move(comp));
  60.         }
  61.     };
  62.  
  63.     // Run Tarjan on every node
  64.     for(int i = 0; i < n; i++){
  65.         if(disc[i] == -1)
  66.             dfs(i);
  67.     }
  68.  
  69.     // Compute answer: sum of min-costs, and product of counts
  70.     ll totalCost = 0;
  71.     ll ways      = 1;
  72.     for(auto &comp : sccs){
  73.         ll mn = LLONG_MAX;
  74.         ll cnt = 0;
  75.         for(int u : comp){
  76.             if(cost[u] < mn){
  77.                 mn = cost[u];
  78.                 cnt = 1;
  79.             } else if(cost[u] == mn){
  80.                 cnt++;
  81.             }
  82.         }
  83.         totalCost += mn;
  84.         ways = ways * cnt % MOD;
  85.     }
  86.  
  87.     cout << totalCost << " " << ways << "\n";
  88.     return 0;
  89. }
  90.  
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin 
3
1 2 3
3
1 2
2 3
3 2
stdout 
3 1
https://ideone.com/a7lEbq
language:
C++ (gcc 8.3)
created:
8 days 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!