Codeforces 427 C

codeforces427C.cpp

#ifndef __MYLIB_H
#define __MYLIB_H

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<climits>
#include<list>
using namespace std;
#endif

#define N 100000
#define MOD 1000000007

int n;
int m;
vector<vector<int> > graph(N), inverseG(N);
int cost[N];
bool vis[N];

void dfs(int a, vector<int>& ret) {
	vis[a] = true;
	for(int i = 0; i < graph[a].size(); i++) {
		if(!vis[graph[a][i]]) {
			dfs(graph[a][i], ret);
		}
	}

	ret.push_back(a);
}

int main() {
	scanf("%d", &n);

	memset(vis, false, sizeof vis);

	for(int i = 0; i < n; i++) {
		scanf("%d", &cost[i]);
	}

	scanf("%d", &m);

	int a, b;
	for(int i = 0; i < m; i++) {
		scanf("%d %d\n", &a, &b);
		a--,b--; // Values are 1 based
		graph[a].push_back(b);
		inverseG[b].push_back(a);
	}

	vector<int> sortedList;
	for(int i = 0; i < n; i++) {
		if(!vis[i]) {
			dfs(i, sortedList);
		}
	}

	memset(vis, false, sizeof vis);

	graph = inverseG;

	long long ret1 = 0, ret2 = 1;
	for(int i = sortedList.size()-1; i >= 0; i--) {

		if(vis[sortedList[i]]) continue;

		vector<int> scc;
		dfs(sortedList[i], scc);

		int mnCost = INT_MAX, cnt = 0;
		for(int i = 0; i < scc.size(); i++) {
			if(cost[scc[i]] < mnCost) {
				mnCost = cost[scc[i]];
				cnt = 1;
			}
			else if(cost[scc[i]] == mnCost) cnt++;
		}

		ret1 += mnCost;
		ret2 *= cnt;
		ret2 %= MOD;
	}

	cout << ret1 << " " << ret2 << endl;
}