fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. const int MOD = 1000000007; 
  6. const int MX  = 1000001;
  7.  
  8. // ─── Modular utilities ───────────────────────────────────────────────────
  9.  
  10. ll modExp(ll base, ll power) {
  11.     if (power == 0) return 1;
  12.     ll cur = modExp(base, power/2);
  13.     cur = (cur * cur) % MOD;
  14.     if (power & 1) cur = (cur * base) % MOD;
  15.     return cur;
  16. }
  17.  
  18. ll inv(ll x) { return modExp(x, MOD-2); }
  19. ll mul(ll a, ll b) { return (a * b) % MOD; }
  20. ll add(ll a, ll b) { a += b; if (a >= MOD) a -= MOD; return a; }
  21. ll sub(ll a, ll b) { a -= b; if (a <  0) a += MOD; return a; }
  22. ll dvd(ll a, ll b) { return mul(a, inv(b)); }
  23. ll ceilDiv(ll a, ll b) { return (a + b - 1) / b; }
  24.  
  25. // (optional) nCr in O(1) after a single initFacs()
  26. ll *facs    = new ll[MX];
  27. ll *facInvs = new ll[MX];
  28.  
  29. void initFacs() {
  30.     facs[0]    = 1;
  31.     facInvs[0] = 1;
  32.     for (int i = 1; i < MX; i++) {
  33.         facs[i]    = facs[i-1] * i % MOD;
  34.         facInvs[i] = inv(facs[i]);
  35.     }
  36. }
  37.  
  38. ll choose(int n, int r) {
  39.     if (r < 0 || r > n) return 0;
  40.     return facs[n] * facInvs[r] % MOD * facInvs[n-r] % MOD;
  41. }
  42.  
  43. // ─── Tarjan’s SCC finder ──────────────────────────────────────────────────
  44.  
  45. void tarjanDFS(int u,
  46.                const vector<vector<int>>& adj,
  47.                vector<int>& disc,
  48.                vector<int>& low,
  49.                vector<bool>& onStack,
  50.                stack<int>& st,
  51.                int& timer,
  52.                vector<vector<int>>& sccs)
  53. {
  54.     disc[u] = low[u] = timer++;
  55.     st.push(u);
  56.     onStack[u] = true;
  57.  
  58.     for (int v : adj[u]) {
  59.         if (disc[v] == -1) {
  60.             tarjanDFS(v, adj, disc, low, onStack, st, timer, sccs);
  61.             low[u] = min(low[u], low[v]);
  62.         }
  63.         else if (onStack[v]) {
  64.             low[u] = min(low[u], disc[v]);
  65.         }
  66.     }
  67.  
  68.     if (low[u] == disc[u]) {
  69.         vector<int> comp;
  70.         while (true) {
  71.             int v = st.top(); st.pop();
  72.             onStack[v] = false;
  73.             comp.push_back(v);
  74.             if (v == u) break;
  75.         }
  76.         sccs.push_back(comp);
  77.     }
  78. }
  79.  
  80. vector<vector<int>> tarjanSCC(int n, const vector<vector<int>>& adj) {
  81.     vector<int>    disc(n, -1), low(n, 0);
  82.     vector<bool>   onStack(n, false);
  83.     stack<int>     st;
  84.     vector<vector<int>> sccs;
  85.     int timer = 0;
  86.  
  87.     for (int i = 0; i < n; i++) {
  88.         if (disc[i] == -1)
  89.             tarjanDFS(i, adj, disc, low, onStack, st, timer, sccs);
  90.     }
  91.     return sccs;
  92. }
  93.  
  94. // ─── main() ───────────────────────────────────────────────────────────────
  95.  
  96. int main(){
  97.     ios::sync_with_stdio(false);
  98.     cin.tie(nullptr);
  99.  
  100.     // If you ever need nCr:
  101.     // initFacs();
  102.  
  103.     int n, m;
  104.     cin >> n >> m;
  105.     vector<int> arr(n);
  106.     for (int i = 0; i < n; i++) {
  107.         cin >> arr[i];
  108.     }
  109.  
  110.     vector<vector<int>> adj(n);
  111.     for (int i = 0; i < m; i++) {
  112.         int u, v;
  113.         cin >> u >> v;
  114.         u --; v --;
  115.         adj[u].push_back(v);
  116.     }
  117.  
  118.     auto sccs = tarjanSCC(n, adj);
  119.  
  120.     ll res1 = 0;
  121.     ll res2 = 1;
  122.     for (auto &comp : sccs) {
  123.         int currMin = INT_MAX;
  124.         int cnt     = 0;
  125.         // find the minimum arr[value] in this SCC and count how many times it appears
  126.         for (int node : comp) {
  127.             if (arr[node] < currMin) {
  128.                 currMin = arr[node];
  129.                 cnt     = 1;
  130.             } else if (arr[node] == currMin) {
  131.                 cnt++;
  132.             }
  133.         }
  134.         res1 = add(res1, currMin);
  135.         res2 = mul(res2, cnt);
  136.     }
  137.  
  138.     cout << res1 << ' ' << res2 << "\n";
  139.     return 0;
  140. }
  141.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
3
1 2 3
3
1 2
2 3
3 2
stdout
copy 
8 1
https://ideone.com/dS94eH
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!