Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <queue>
- #include <cmath>
- #include <stack>
- #include <iomanip>
- #include <bitset>
- #define szybcior ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- const ll inf = 10e17;
- const ll M = 1000000007;
- const ll ile = 100008;
- ll n,m;
- ll koszt[ile];
- ll post[ile];
- vector<ll> v[ile];
- vector<ll> v1[ile];
- bitset<ile> bo;
- bitset<ile> bo1;
- ll czas = 0;
- pair<ll,ll> ans = {0,1}; // koszst | ilosc mozliwosci
- void dfs(ll start)
- {
- bo[start] = true;
- // cout << "wierzcholek " << start << "\n";
- for(auto it: v[start])
- if(!bo[it])
- dfs(it);
- post[++czas] = start;
- }
- // ll dfs1(ll start)
- // {
- // bo1[start] = true;
- // ll wartosc = koszt[start];
- // // cout << "wierzcholek " << start << "\n";
- // for(auto it: v1[start])
- // if(!bo1[it])
- // {
- // ll pomoc = dfs1(it);
- // if(pomoc == wartosc) ilosc++;
- // else if(pomoc < wartosc)
- // {
- // cout << "ZMIEJSZANIE " << wartosc << " na " << pomoc << " ";
- // ilosc = 1;
- // wartosc = pomoc;
- // }
- // ilosc %= M;
- // }
- // cout << start << ": " << ilosc << " wartosc: " << wartosc << "\n";
- // return wartosc;
- // }
- void dfs1(ll v, ll& cand, ll& cnt) {
- bo1[v] = true;
- cnt %= M;
- if(koszt[v] < cand)
- cand=koszt[v], cnt=0;
- for(auto && it: v1[v])
- if(!bo1[it])
- dfs1(it, cand, cnt);
- if(koszt[v] ==cand)
- cnt++, cnt %= M;
- cnt %= M;
- }
- int main()
- {
- szybcior;
- cin >> n;
- for(int i = 1; i <= n; i++)
- cin >> koszt[i];
- cin >> m;
- for(int i = 0; i < m; i++)
- {
- ll a,b;
- cin >> a >> b;
- v[a].push_back(b);
- v1[b].push_back(a);
- }
- for(int i = 1; i <= n; i++)
- if(!bo[i])
- dfs(i); // ustawienie post orderu
- // for(int i = 1; i <= n; i++) cout << i << ": " << post[i] << "\n";
- for(int i = n; i > 0; i--)
- {
- // cout << 'x';
- if(!bo1[post[i]])
- {
- ll ile =-1, mini = inf ;
- dfs1(post[i], mini, ile);
- // cout << mini << " " << ile << "\n";
- ans.first += mini;
- ans.second *= (ile % M);
- ans.second %= M;
- }
- }
- cout << ans.first << " " << ans.second << " ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement