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
#include <cstdio>
#include <vector>

#define NAJW_SUBSTANCJI 200 ## 000
#define NAJW_REAKCJI 500 ## 000

struct roztwor {
	int pokolenie;
	roztwor *produkt;
	std::vector<int> *reakcje;
};

int masaSubstancji[NAJW_SUBSTANCJI+1];
roztwor roztwory[2 * NAJW_SUBSTANCJI];
int reakcje[NAJW_REAKCJI][2];
int obecnie[NAJW_SUBSTANCJI+1];

int main()
{
	int fiolek, przelan, reakcyj, a, b, i;
	roztwor *r1, *r2;
	long long wynik = 0;

	scanf("%d %d %d", &fiolek, &przelan, &reakcyj);

	for (i=1;i<=fiolek;++i)
	{
		scanf("%d", &masaSubstancji[i]);
		obecnie[i] = i;
	}

	for (i=1;i<=przelan;++i)
	{
		scanf("%d %d", &a, &b);
		roztwory[obecnie[a]].produkt = roztwory[obecnie[b]].produkt = &roztwory[fiolek+i];
		obecnie[b] = fiolek+i;
		roztwory[fiolek+i].reakcje = new typeof(*roztwory[fiolek+i].reakcje);
	}

	for (i=przelan+fiolek;i>0;--i)
		roztwory[i].pokolenie = roztwory[i].produkt!=NULL? roztwory[i].produkt->pokolenie+1: 0;

	for (i=0;i<reakcyj;++i)
	{
		scanf("%d %d", &reakcje[i][0], &reakcje[i][1]);

		r1 = &roztwory[reakcje[i][0]];
		r2 = &roztwory[reakcje[i][1]];

		while (r1->pokolenie > r2->pokolenie)
			r1 = r1->produkt;

		while (r1->pokolenie < r2->pokolenie)
			r2 = r2->produkt;

		while (r1!=NULL && r2!=NULL)
		{
			if (r1 == r2)
			{
				r1->reakcje->push_back(i);
				break;
			}
			else
			{
				r1 = r1->produkt;
				r2 = r2->produkt;
			}
		}
	}

	for (i=1;i<=przelan;++i)
	{
		for (typeof(roztwory[fiolek+i].reakcje->begin()) it = roztwory[fiolek+i].reakcje->begin();it != roztwory[fiolek+i].reakcje->end();++it)
		{
			a = reakcje[(*it)][0];
			b = reakcje[(*it)][1];

			if (masaSubstancji[b] > masaSubstancji[a])
			{
				a ^= b;
				b ^= a;
				a ^= b;
			}

			wynik += 2 * masaSubstancji[b];
			masaSubstancji[a] -= masaSubstancji[b];
			masaSubstancji[b] = 0;
		}
	}
	printf("%lld\n", wynik);

	return 0;
}