1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
// Fiolki.cpp : Defines the entry point for the console application.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;


class reakcja
{public:
	int sub1; // sub1, sub2 - substraty reakcji (numery substancji reagujacych)
	int sub2;
	int priorytet;
	reakcja(int s1, int s2, int p) {sub1 = s1; sub2 = s2; priorytet = p;}
	bool operator < (const reakcja & other) const {return priorytet < other.priorytet;}
};

class fiolka
{
public:
	map<int,int> zawartosc; // kazdemu numerowi substancji w fiolce przyporzadkowana jest jej masa

	void dodaj (int nr_subst, int masa) 
		{zawartosc[nr_subst] = masa;}
	void przelej (fiolka & other) 
		{zawartosc.insert(other.begin(), other.end()); other.zawartosc.clear();}
	fiolka() {};
	typedef map<int, int>::iterator iterator;
	typedef map<int, int>::const_iterator const_iterator;
	iterator begin() { return zawartosc.begin(); }
	iterator end() { return zawartosc.end(); }
	int size(){return zawartosc.size();}
	iterator find(int nr_subst) {return zawartosc.find(nr_subst);}
private:
	void zmniejsz_mase (iterator sub, int ile)
	{
		sub->second -= ile; 
		if (sub->second == 0) zawartosc.erase(sub); 
	}
public:
	int masa(map<int,int>::iterator sub)
		{return sub->second;}
	long long int reaguj(int nr_sub1, int nr_sub2)
	{
		long long int masa_osadu = 0;
		iterator s1 = zawartosc.find(nr_sub1);
		iterator s2 = zawartosc.find(nr_sub2);
		if (s1 != end() && s2 != end())
		{
			int m = min(masa(s1), masa(s2));
			masa_osadu = 2*m;
			zmniejsz_mase(s1, m);
			zmniejsz_mase(s2, m);
		}		
		return masa_osadu;
	}
};

typedef map<int, map<int, int>> slownik_par;


vector<reakcja> znajdz_reakcje(fiolka & f1, fiolka & f2, const slownik_par & pary)
{
	// dla kazdej substancji z fiolki f1 szukamy w mapie "pary" substancji, z ktorymi ona reaguje
	// i sprawdzamy czy ktores z nich znajduja sie w fiolce f2 -> jesli tak -> dodaj reakcje do kolejnosc_reakcji
	vector<reakcja> kolejnosc_reakcji; 
	for (fiolka::iterator s1 = f1.begin(); s1 != f1.end(); ++s1)
	{
		int nr_sub1 = s1->first;
		slownik_par::const_iterator szukaj = pary.find(nr_sub1); 
		if (szukaj != pary.end()) 
		{
			map<int, int> reagenty = szukaj->second;
			if (reagenty.size() <= f2.size())
				for(map<int,int>::const_iterator s2 = reagenty.begin(); s2 != reagenty.end(); ++s2) // dla kazdego reagenta substancji s1 sprawdzamy czy znajduje sie w fiolce f2
				{
					int nr_sub2 = s2->first;
					int priorytet = s2->second;
					fiolka::iterator szukaj = f2.find(nr_sub2);
					if (szukaj != f2.end())
						kolejnosc_reakcji.push_back(reakcja(nr_sub1, nr_sub2, priorytet));
				}
			else
				for(fiolka::iterator s2 = f2.begin(); s2 != f2.end(); ++s2) // dla kazdej substancji z fiolki f2 sprawdzamy czy jest reagentem substancji s1
				{
					int nr_sub2 = s2->first;
					map<int,int>::const_iterator szukaj = reagenty.find(nr_sub2);
					if (szukaj != reagenty.end())
					{
						int priorytet = szukaj->second;
						kolejnosc_reakcji.push_back(reakcja(nr_sub1, nr_sub2, priorytet));
					}
				}
		}
	}	
	return kolejnosc_reakcji;
}

long long int zmieszaj_fiolki(fiolka & f1, fiolka & f2, const slownik_par & pary)
{
	// funkcja obsluguje zmieszanie zawartosci fiolek f1 i f2 oraz zwraca mase straconego osadu

	long long int masa_osadu = 0;
	vector<reakcja> kolejnosc_reakcji; // struktura pomocnicza - porzadek zachodzenia reakcji w fiolce

	if (f1.size() <= f2.size())
		kolejnosc_reakcji = znajdz_reakcje(f1, f2, pary);
	else
		kolejnosc_reakcji = znajdz_reakcje(f2, f1, pary); // iterowanie po substancjach w fiolce z mniejsza zawartoscia
	
	// przeprowadzenie reakcji zgodnie z kolejnoscia priorytetow
	sort(kolejnosc_reakcji.begin(), kolejnosc_reakcji.end());
	f2.przelej(f1); // przelanie zawartosci fiolki f1 do fiolki f2
	for (int ii=0; ii<kolejnosc_reakcji.size(); ii++)
	{
		int nr_sub1 = kolejnosc_reakcji[ii].sub1;
		int nr_sub2 = kolejnosc_reakcji[ii].sub2;
		masa_osadu += f2.reaguj(nr_sub1, nr_sub2);
	}

	return masa_osadu;
}




int main()
{
	int ile_fiolek, ile_krokow, ile_par;
	cin >> ile_fiolek >> ile_krokow >> ile_par;

	vector<fiolka> fiolki(ile_fiolek, fiolka()); // kazdej filce oodpowiada mapa numerow substancji znajdujacych sie w fiolce i przyporzadkowanych im mas

	for (int n=1; n <= ile_fiolek; n++)
	{
		int masa; cin >> masa;
		fiolki[n-1].dodaj(n, masa); // przyporzadkowanie masy n-tej substancji w n-tej fiolce (index n-1)
	}

	vector<pair<int,int>> kroki;

	for (int m=1; m <= ile_krokow; m++)
	{
		int a, b; cin >> a >> b;
		kroki.push_back(make_pair(a,b));
	}

	map<int, map<int, int>> pary_reagentow;  
	for (int k=1; k <= ile_par; k++)
	{
		int a, b; cin >> a >> b;
		pary_reagentow[a][b] = k; // przypisanie priorytetu reakcji danej parze reagentow
		pary_reagentow[b][a] = k;
	}

	long long int masa_osadu = 0;

	for (int ii = 0; ii < ile_krokow; ii++)
	{
		// indeksy fiolek do zmieszania:
		int n1 = kroki[ii].first -1;
		int n2 = kroki[ii].second -1;
		masa_osadu += zmieszaj_fiolki(fiolki[n1], fiolki[n2], pary_reagentow);
	}

	cout << masa_osadu;

	return 0;
}