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
#include<iostream>
#include <algorithm>
#include <stdlib.h>
#include<set>
using namespace std;
#define M2 200002
#define M5 500005
struct CzegoIle { int czego; int ile;};
bool Por(const CzegoIle& a1, const CzegoIle& a2) { return a1.czego<a2.czego;};
typedef set<CzegoIle,bool(*)(const CzegoIle&, const CzegoIle&)>::iterator iter;
set<CzegoIle,bool(*)(const CzegoIle&, const CzegoIle&)> W[M2];

struct React { int first; int second; int which;};
bool CheckIf(const React& a1, const React& a2) {
   if(a1.first!=a2.first)   return a1.first<a2.first;
   else                     return a1.second<a2.second;
};
typedef set<React,bool(*)(const React&, const React&)>::iterator kukaj;
set<React, bool(*)(const React&,const React&)> re(&CheckIf);

int main( )
{
   set<int> jjj;
   set<int>::iterator it;
  // ios_base::sync_with_stdio(0);
   int masy, kroki, pary, tempy, k;
   long long wynik=0;
   int ZE[M2], DO[M2], PA[M5], RA[M5];
   for(int i=0; i<M2; ++i)
      W[i]=set<CzegoIle,bool(*)(const CzegoIle&, const CzegoIle&)> (&Por);
                                                   /*W[i] tablica zbiorów par*/
   CzegoIle Temp1, Temp2;
   React temp;
   iter it1, it2;
   kukaj ttt;
   cin >> masy >> kroki >> pary;
   for(int j=1; j<=masy; ++j) {
      Temp1.czego=j;
      cin >> Temp1.ile;                            /*masa subst. "j" we fiolce "j"*/   
      W[j].insert(Temp1);
   }
   for(int i=1; i<=kroki; ++i) 
      cin>>ZE[i]>>DO[i];                          /*kolejne przelewy*/
   for(int k=1; k<=pary; ++k){
      cin >> PA[k] >> RA[k];                      /*pary reagujące ze sobą (od max)*/
      temp.first=min(PA[k],RA[k]);
      temp.second=max(PA[k],RA[k]);
      temp.which=k;
      re.insert(temp);
      temp.first=max(PA[k],RA[k]);
      temp.second=min(PA[k],RA[k]);
      temp.which=k;
      re.insert(temp);
   }
   
   for(int i=1; i<=kroki; ++i) {
      for (it1=W[ZE[i]].begin(); it1!=W[ZE[i]].end(); ++it1)
         W[DO[i]].insert(*it1);
      
      for (it1=W[DO[i]].begin(); it1!=W[DO[i]].end(); ++it1) {
         for (it2=it1; it2!=W[DO[i]].end(); ++it2) {
            temp.first=(*it1).czego;
            temp.second=(*it2).czego;
            ttt=re.find(temp);
            if(ttt != re.end()) {   
               jjj.insert((*ttt).which);
            }
         }
      }
      for(it = jjj.begin(); it!=jjj.end(); ++it){
         k = *it;
            Temp1.czego=PA[k];
            Temp2.czego=RA[k];
            it1 = W[DO[i]].find(Temp1);
            it2 = W[DO[i]].find(Temp2);
            if( (it1 != W[DO[i]].end()) && (it2 != W[DO[i]].end()) ) {
               wynik+=(min( (*it1).ile , (*it2).ile ))*2;
               if((*it1).ile>(*it2).ile) {
                  Temp1.czego=(*it1).czego;
                  Temp1.ile=(*it1).ile-(*it2).ile;
               }
               else {
                  Temp1.czego=(*it2).czego;
                  Temp1.ile=(*it2).ile-(*it1).ile;
               }
               W[DO[i]].erase(*it2);
               W[DO[i]].erase(*it1);
               if(Temp1.ile)
                  W[DO[i]].insert(Temp1);
            }
         }
      }      
   cout<<wynik<<endl;
   return 0;
}