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
#include<iostream>

using namespace std;

int ilosc[200001]; //ilosc kazdej substancji

int node[400001][2]; //0 - przechodzuje adres kolejnego noda, 1 - przechowuje wskaxnik na reakcje
int pnode[200001]; //pozwala dobrać się do noda, po numerze fiolki

int reak[500001][3]; //0 - skladnik 1, 1 - skladnik 2, 2 - adres następnej reakcji w nodzie

int kol[200000][2];

int main()
{
   ios_base::sync_with_stdio(0);
   int n, m, k;
   cin >> n;
   cin >> m;
   cin >> k;
   for(int i = 1; i <= n; i++)
   {
      cin >> ilosc[i];
      pnode[i] = i;
   }
   
   //budujemy drzewo reakcji
   for(int i = 1; i <= m; i++)
   {
      cin >> kol[i][0];
      cin >> kol[i][1];
      
      node[pnode[kol[i][0]]][0] = n + i; //skladnik laduje w nodzie n + i
      node[pnode[kol[i][1]]][0] = n + i; //skladnik laduje w nodzie n + i 
      pnode[kol[i][1]] = n + i; //aders fiolki do której przelaliśmy
   }
   
   //ustawiomy reakcje w nodach
   for(int i = 1; i <= k; i++)
   {
      cin >> reak[i][0];
      cin >> reak[i][1];
      
      //szukamy noda
      int curr_node1 = reak[i][0];
      int curr_node2 = reak[i][1];
      
      while(curr_node1 != curr_node2 && curr_node1 != 0 && curr_node2 != 0)
      {
         if(node[curr_node1][0] == node[curr_node2][0])
         {
            curr_node1 = node[curr_node1][0];
            curr_node2 = node[curr_node2][0];
         }
         else if(node[curr_node1][0] < node[curr_node2][0])
            curr_node1 = node[curr_node1][0];
         else
            curr_node2 = node[curr_node2][0];
      }
      
      if(curr_node1 == 0 || curr_node2 == 0)
         continue; //substancje nie mają mozliwosci przereagowania
      
      int curr_reak = node[curr_node1][1];
      
      if(curr_reak == 0)
         node[curr_node1][1] = i;
      else //szuamy ostatniej reakcji, i dokladamy nastepna
      {
         while(reak[curr_reak][2] != 0)
         {
            curr_reak = reak[curr_reak][2];
         }
         reak[curr_reak][2] = i;
      }
   }
   
   //obliczamy osad
   long long int osad = 0;
   
   for(int i = 1; i <= m; i++) //reagujemy w poszczególnych nodach
   {      
      int curr_reak = node[n + i][1];
      while(curr_reak != 0) // reagujemy dopuki mamy reakcje w nodzie
      {
         int idx1 = reak[curr_reak][0]; //skladnik reakcji 1
         int idx2 = reak[curr_reak][1]; //skladnik reakcji 2
         
         int min = ilosc[idx1] < ilosc[idx2] ? ilosc[idx1] : ilosc[idx2];
         osad += 2 * min;
         ilosc[idx1] -= min;
         ilosc[idx2] -= min;
         
         curr_reak = reak[curr_reak][2];//nastepna reakcja w nodzie
      }
   }
   
   cout << osad<<endl;
}