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
//Autor: Mateusz Wasylkiewicz
//Zawody: Potyczki Algorytmiczne 2014
//Strona: http://potyczki.mimuw.edu.pl/
//Zadanie: Fiolki, runda 5B
//Czas: O((m+k)*log(m)+k)
//Opis:
//	Symuluje eksperyment, spisujac dla kazdej subtancji jej historie zmiany fiolek. Nastepnie dla
//	kazdej pary reagujacych ze soba substancji, na podstawie tej historii oblicza czas, w ktorym
//	dojdzie miedzy nimi do reakcji. Pozniej, na tej podstawie symuluje wytracanie sie osadu
//	w trakcie eksperymentu.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

typedef long long LL;
#define FOR(x, a, b) for (LL x = (a); x <= (b); x++)
#define REP(x, n) for (LL x = 0; x < (n); x++)
#define ALL(c) (c).begin(), (c).end()
#define PB push_back
#define SIZE(c) LL((c).size())

struct Substancje //reprezentuje pare substancji reagujacych ze soba
{
	LL a, b, t, nr; //a, b - numery substancji, t - czas ich reakcji, nr - numer pary
	
	inline void wczytaj(LL nowy_nr)
	{
		nr = nowy_nr;
		cin >> a >> b;
		a--;
		b--;
	}
	
	inline bool operator < (const Substancje& dane) const
	{
		if (t == dane.t)
			return nr < dane.nr;
		return t < dane.t;
	}
};

const LL MAX_N = 200100, MAX_K = 500100, INF = 1100000000;
LL n, m, k, fiolka[MAX_N]; //m - ilosc przelan, fiolka[0..n) - fiolki
Substancje sub[MAX_K]; //sub[0..k) - pary substancji reagujacych ze soba

namespace UF
{
	struct Zmiana //reprezentuje zmiane nr zbioru pewnego elementu
	{
		Zmiana(LL nowy_nr, LL nowy_czas) : nr(nowy_nr), czas(nowy_czas) {} 
		LL nr, czas; //nr - numer nowego zbioru, czas - czas przejscia
	};
	
	vector<LL> zbior[MAX_N]; //zbior[i] - zbior elementow nalezacych do zbioru i
	vector<Zmiana> el[MAX_N]; //el[i] - historia przejsc elementu i
	
	void przygotuj_sie()
	{
		REP(i, n)
			zbior[i].PB(i);
		REP(i, n)
			el[i].PB(Zmiana(i, 0));
	}
	
	//Przerzuca wszystkie elementy ze zbioru a do zbioru b i ustawia ich czasy przejscia na t.
	inline void przerzuc_zbior(LL a, LL b, LL t)
	{
		REP(i, SIZE(zbior[a]))
		{
			LL c = zbior[a][i];
			el[c].PB(Zmiana(b, t));
		}
		zbior[b].insert(zbior[b].end(), ALL(zbior[a]));
		zbior[a].clear();
	}
	
	//Laczy ze soba zbiory, do ktorych naleza elementy a i b.
	inline void polacz(LL a, LL b)
	{
		static LL t = 1;
		a = el[a].back().nr;
		b = el[b].back().nr;
		if (SIZE(zbior[a]) < SIZE(zbior[b]))
			przerzuc_zbior(a, b, t);
		else
			przerzuc_zbior(b, a, t);
		t++;
	}
	
	inline LL czas_reakcji(LL a, LL b)
	{
		if (el[a].back().nr != el[b].back().nr)
			return INF;
		
		LL i = SIZE(el[a])-1, j = SIZE(el[b])-1;
		while (i >= 1 && j >= 1 && el[a][i-1].nr == el[b][j-1].nr)
		{
			i--;
			j--;
		}
		return max(el[a][i].czas, el[b][j].czas);
	}
}

void wczytaj_fiolki()
{
	cin >> n >> m >> k;
	REP(i, n)
		cin >> fiolka[i];
}

//Symuluje eksperyment, spisujac historie zmian zbiorow substancji w jednej fiolce.
void eksperymentuj()
{
	REP(i, m)
	{
		LL a, b;
		cin >> a >> b;
		UF::polacz(--a, --b);
	}
}

void wczytaj_substancje_reagujace()
{
	REP(nr, k)
		sub[nr].wczytaj(nr);
}

void wyznacz_czasy_reakcji()
{
	REP(i, k)
		sub[i].t = UF::czas_reakcji(sub[i].a, sub[i].b);
}

//Zwraca ilosc osadu wytracana w czasie calego eksperymentu.
LL wytracaj_osad()
{
	LL osad = 0;
	REP(i, k)
		if (sub[i].t < INF)
		{
			LL a = sub[i].a, b = sub[i].b;
			LL pom = min(fiolka[a], fiolka[b]);
			fiolka[a] -= pom;
			fiolka[b] -= pom;
			osad += 2 * pom;
		}
	return osad;
}

void zrob_test()
{
	wczytaj_fiolki();
	UF::przygotuj_sie();
	eksperymentuj();
	wczytaj_substancje_reagujace();
	wyznacz_czasy_reakcji();
	sort(sub, sub + k);
	cout << wytracaj_osad() << '\n';
}

int main()
{
	ios_base::sync_with_stdio(0);
	zrob_test();
	return 0;
}