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
/*#ifdef _MSC_VER
  #ifndef __GNUC__
    #pragma warning(disable: 4996)
  #endif
  #define main main0
#endif//*/
#include <cstdio>
#include <algorithm>
#include <list>
#include <map>
using namespace std;

typedef list<int> listInt;
typedef map<int, int> mapInt2Int;

const int NMax = 200000;
const int KMax = 500000;

struct Reaction {
  int substance1;
  int substance2;
};

struct Step {
  listInt* phial1;
  listInt* phial2;
};

listInt Phials[NMax+1];
int Weights[NMax+1];
Step Steps[NMax];
int Orders[KMax];
mapInt2Int MapsSubst2Subst[NMax+1];
Reaction Reactions[KMax];

bool pred_remove(const int val) { return Weights[val] <= 0; }

long long DoReactions(const Step* const step, int orders);

int FindReactions(const Step* const step);

void Read(Step*& endSteps);

int main() {
  long long result = 0;
  Step* endSteps;

  Read(endSteps);

  for(Step *step = Steps; step < endSteps; ++step) {
    int orders = FindReactions(step);
    result += DoReactions(step, orders);
  }//*/

  printf("%lld\n", result);
  return 0;
}

long long DoReactions(const Step* const step, int orders) {
  long long result = 0;
  for(int i = 0; i < orders; ++i) {
    int substance1 = Reactions[Orders[i]].substance1;
    int substance2 = Reactions[Orders[i]].substance2;
    int weight = Weights[substance1] < Weights[substance2] ? Weights[substance1]: Weights[substance2];
    result += 2 * weight;
    Weights[substance2] -= weight;
    Weights[substance1] -= weight;
  }
  step->phial2->splice(step->phial2->begin(), *step->phial1);
//  step->phial2->remove_if(pred_remove);//(bind2nd(less_equal<int>(), 0));

  return result;
}//*/

int FindReactions(const Step* const step) {
  int orders = 0;
  listInt::iterator endSubst1 = step->phial1->end();
  listInt::iterator endSubst2 = step->phial2->end();

  for(listInt::iterator subst2 = step->phial2->begin(); subst2 != endSubst2; ++subst2) {
    if(Weights[*subst2] <= 0)
      if((subst2 = step->phial2->erase(subst2)) == endSubst2)
        break;
    mapInt2Int* react2 = MapsSubst2Subst + *subst2;
    for(listInt::iterator subst1 = step->phial1->begin(); subst1 != endSubst1; ++subst1) {
      if(Weights[*subst1] <= 0)
        continue;
      mapInt2Int::iterator StepsIter = react2->find(*subst1);
      if(StepsIter == react2->end())
        continue;
      Orders[orders++] = StepsIter->second;
//      react2->erase(StepsIter);
    }
  }

  sort(Orders, Orders + orders);
  return orders;
}

void Read(Step*& endSteps) {
  int n, m, k;

  scanf("%d%d%d", &n, &m, &k);
  endSteps = Steps + m;

  /*for(int i = 1; i < n; ++i) {
    Phials[i].clear();
    MapsSubst2Subst[i].clear();
  }//*/

  for(int i = 1; i <= n; ++i) {
    scanf("%d", Weights + i);
    Phials[i].push_back(i);
  }

  for(int i = 0; i < m; ++i) {
    int phial1, phial2;
    scanf("%d%d", &phial1, &phial2);
    /*if(phial1 == phial2)
      phial1=phial1;//*/
    Steps[i].phial1 = Phials + phial1;
    Steps[i].phial2 = Phials + phial2;
  }

  for(int i = 0; i < k; ++i) {
    int substance1, substance2;
    scanf("%d%d", &substance1, &substance2);
    /*if(substance1 == substance2)
      substance1=substance1;//*/
    Reactions[i].substance1 = substance1;
    Reactions[i].substance2 = substance2;
    MapsSubst2Subst[substance1].insert(make_pair(substance2, i));
    MapsSubst2Subst[substance2].insert(make_pair(substance1, i));
  }
}