Fedor and Essay

Fedor and Essay

time limit per test:2 seconds
memory limit per test:256 megabytes
input:standard input
output:standard output


Fedor'un İngilizce öğretmeni ondan bir kompozisyon hazırlamasını istedi. Fakat Fedor bu konuda çok isteksiz olduğundan Alex'ten yardım istedi. Alex onun için bir kompozisyon yazdı fakat Fedor Alex'in yazdığı kompozisyonu pek beğenmedi. Bunun üzerine Fedor İngilizce Eşanlamlı kelimeler sözlüğünü kullanarak Alex'in yazdığı kompozisyonu değiştirmeye karar verdi.

Fedor kompozisyonun kelimelerini değiştirmek istiyor fakat anlamının aynı kalmasını istiyor. Bu yüzden yapabileceği tek değişiklik kompozisyondan bir kelimeyi -sözlükteki değiştirme kurallarını baz alarak- o kelimenin eş anlamlısıyla değiştirmektir. Fedor bu işlemi dilediği kadar yapabilir.

Sonuç olarak, Fedor içinde mümkün olduğunca az «R» harfi geçen bir kompozisyon elde etmek istiyor (büyük-küçük harf farketmeksizin). Eğer minumum «R» harfi ile oluşturulabilecek birden fazla kompozisyon varsa bunlar arasından en kısa olanını seçiyor (bir yazının uzunluğu içindeki bütün kelimelerin uzunlukları toplamıdır). Fedor'a istenilen kompozisyonu yazması için yardım edin.

Bu soruda harflerin büyük ya da küçük olması önemli değildir. Eğer sözlüğe göre "cat" kelimesi ile "DOG" kelimesi yer değiştirebiliyorsa, bu demektir ki "Cat" ve "doG" da yer değiştirebilir,



Girdi

İlk satırda başlangıçtaki kompozisyonun kelime sayısı olan m (1 ≤ m ≤ 100.000) değeri yazar. İkinci satırda kompozisyondaki kelimeler yazar. Kelimeler birer boşlukla ayrılmıştır ve kelimelerin toplam uzunluğunun 100.000 i geçmeyeceği kesindir.

Bir dahaki satırda eşanlamlı kelime çifti sayısı olan n (0 ≤ n ≤ 100.000) yazar. Bir dahaki n satırda i. satır bir boşlukla ayrılmış iki tane (xi, yi) en az 1 harfli kelime içerir. Bunun anlamı xi kelimesinin yerine yi kelimesinin geçebileceğidir (tersi durum için geçerli değildir). Kelime ikililerinin uzunlukları toplamı 500.000 harfi geçmeyeceği garanti edilmektedir.

Girdideki bütün kelimeler sadece İngiliz alfabesindeki küçük veya büyük harflerden oluşur.

Çıktı

Tek satırda iki tam sayı - oluşacak en iyi durumdaki kompozisyondaki «R» harfi sayısı ve bu kompozisyonun uzunluğu.

Örnek

girdi

3
AbRb r Zz
4
xR abRb
aA xr
zz Z
xr y

çıktı

2 6


girdi

2
RuruRu fedya
1
ruruRU fedor

çıktı

1 10

-------------------------------------------------------------------------------------------------------------------------

Yollanabilecek link:

http://codeforces.com/problemset/problem/467/D

-------------------------------------------------------------------------------------------------------------------------

Çözüm
İlk olarak farketmemiz gereken şey sorunun stringler le hiçbir alakasının olmadığıdır yani her string için önemli olan sadece 2 şey vardır : 1- String teki R harfi sayısı 2- Stringin uzunluğu.

İkinci önemli nokta ise soruda belirtilmemesine rağmen girdide aynı kelimelerin kullanılabileceği unutulmamalıdır. Bunun çözüm yolumuza bir etkisi olmayacaktır fakat kullanacağımız veri yapılarını yanlış seçmemek için önemlidir.

Çözüme gelecek olursak öncelikle yapmamız gereken şey soruda verilen her kelimeyi bir node olarak düşünüp bir graph oluşturmaktır. Her node un bir numarası bir de pair değeri olmalıdır bu pair değer sırasıyla R harfi sayısını ve kelimenin uzunluğunu tutmalıdır. Görüldüğü üzere son yapmamız gereken şey kompozisyondaki her node u pair değeri mümkün olduğunca küçük bir node ile değiştirmektir, ancak değiştirme işlemi 1 ile sınırlı değildir yani bir a kelimesini ilk önce b ile b'yi de daha sonra d ile değiştirebiliriz.

Gelelim graph'ımızı oluşturmaya; graph'ı bize verilen n tane eş anlamlı kelime çiftini kullanarak oluşturmalıyız verilen bir a b kelime çifti için a dan b ye yol varmış gibi düşünebiliriz. Fakat a ve b birer kelime olduğu için bu kelimelerin orjinal komposizyonda geçtiği indis numarasını oluşturacağımız node'un numarası yapmalıyız (bir kelimenin birden fazla yerde geçebileceği unutulmamalıdır). a b çiftinde orjinal kompozisyonumuzda olmayan bir kelime varsa da bu kelimeye n den büyük yeni bir node numarası verebiliriz. Mesela şu şekildeki bir girdi için:
3
ral ral kal
4
ral tal
ral kal
tal zal
kal tal
Graph'mızdaki yolları sırasıyla şöyle oluşturmalıyız:
İlk çift için 1'den 4'e ve 2'den 4'e
İkinci çift için 1'den 3'e ve 2'den 3'e
Üçüncü çift için 4'ten 5'e
Dördüncü çift için 3'ten 4'e yol olur.

Graph'imizi oluşturduktan 1'den N'e kadar olan her node için şu soruya cevap vermeliyiz: Her node'dan ulaşabileceğimiz minumum değerli node'un değeri ne (pair değeri) ve bu node ları kendimizin yerine koymalıyız.
Eğer yapımız bir tree veya DAG(directed acyclic graph) olsaydı bu soruyu basit bir DFS ile cevaplayabilirdik fakat şu anki durumda yapıda döngüler olabileceği için bu soruya O(N) de cevap veremeyiz. O halde ne duruyoruz yapıyı DAG ' e çevirelim.

Yapıyı DAG'e çevirmek için kullanacağımız yöntem SCC olacaktır. Yapıda bütün SCC leri bulduktan sonra artık nodeları değil de SCC leri birbirine bağlarız. Bir scc nin değeri ise o SCC yi oluşturan node'ların değerlerinin en küçüğü olur bu durumun sebebi SCC deki her node'dan her node'a ulaşabileceğimiz için bir kelimeyi o SCC'deki her hangi bir kelimeyle değiştirebiliriz.

-------------------------------------------------------------------------------------------------------------------------
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <string>

using namespace std;

struct node {
node *next;
int where;
} *first[200001], a[200001];

map<string, int> events;

int c[200001], w[200001][2], in[200001], total, n, m, l, A[200001][2],
v[200001][2], dfn[200001], low[200001], pos[200001], len, cnt, num,
color[200001];
string str[100001];

inline void makelist(int x, int y) {
a[++l].where = y;
a[l].next = first[x];
first[x] = &a[l];
}

inline void tarjan(int now) {
dfn[now] = low[now] = ++cnt;
c[++len] = now;
pos[now] = len;
for (node *x = first[now]; x; x = x->next)
if (!dfn[x->where])
tarjan(x->where), low[now] = min(low[now], low[x->where]);
else if (!color[x->where])
low[now] = min(low[now], dfn[x->where]);
if (low[now] == dfn[now]) {
++num;
for (int i = pos[now]; i <= len; i++)
color[c[i]] = num;
len = pos[now] - 1;
}
}

int calc(string str) {
int len = str.size();
for (int i = 0; i < len; i++)
if (str[i] >= 'A' && str[i] <= 'Z')
str[i] = str[i] - 'A' + 'a';
if (events.find(str) != events.end())
return events[str];
events[str] = ++total;
A[total][0] = 0;
A[total][1] = len;
for (int i = 0; i < len; i++)
if (str[i] == 'r')
++A[total][0];
return total;
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
cin >> str[i];
scanf("%d", &m);
memset(first, 0, sizeof(first));
l = 0;
events.clear();
total = 0;
for (int i = 1; i <= m; ++i) {
string str;
cin >> str;
int x = calc(str);
cin >> str;
int y = calc(str);
makelist(x, y);
w[i][0] = x;
w[i][1] = y;
}
memset(color, 0, sizeof(color));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
cnt = len = num = 0;
for (int i = 1; i <= total; i++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= num; i++)
v[i][0] = v[i][1] = 1 << 30;
for (int i = 1; i <= total; i++) {
int j = color[i];
if (A[i][0] < v[j][0] || (A[i][0] == v[j][0] && A[i][1] < v[j][1]))
v[j][0] = A[i][0], v[j][1] = A[i][1];
}
memset(first, 0, sizeof(first));
l = 0;
memset(in, 0, sizeof(in));
for (int i = 1; i <= m; i++)
if (color[w[i][0]] != color[w[i][1]])
makelist(color[w[i][0]], color[w[i][1]]), ++in[color[w[i][1]]];
int k = 0;
for (int i = 1; i <= num; i++)
if (!in[i])
c[++k] = i;
for (int l = 1; l <= k; l++) {
int m = c[l];
for (node *x = first[m]; x; x = x->next)
if (!--in[x->where])
c[++k] = x->where;
}
for (int i = num; i; i--) {
int m = c[i];
for (node *x = first[m]; x; x = x->next) {
int j = x->where;
if (v[j][0] < v[m][0] || (v[j][0] == v[m][0] && v[j][1] < v[m][1]))
v[m][0] = v[j][0], v[m][1] = v[j][1];
}
}
long long ans1 = 0, ans2 = 0;
for (int i = 1; i <= n; i++) {
int Q = str[i].size();
for (int j = 0; j < Q; j++)
if (str[i][j] >= 'A' && str[i][j] <= 'Z')
str[i][j] = str[i][j] - 'A' + 'a';
if (events.find(str[i]) == events.end()) {
ans2 += Q;
for (int j = 0; j < Q; j++)
if (str[i][j] == 'r')
++ans1;
} else {
int j = color[events[str[i]]];
ans1 += v[j][0];
ans2 += v[j][1];
}
}
cout << ans1 << " " << ans2 << endl;
return 0;