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
#include <iostream>
#include <vector>
#include <set>
using namespace std;

typedef unsigned long long int big;

struct krok {
    big z;
    big d;
};

struct reakcja {
    big prio;
    big a;
};

struct akcja {
    big prio;
    big a;
    big b;
};

struct comp {
    bool operator()(const reakcja &l, const reakcja &g) {
        return l.a<g.a;
    }
};

struct acomp {
    bool operator()(const akcja &l, const akcja &g) const {
        return l.prio<g.prio;
    }
};

int main(){
    big i,n,m,k,c,d,osad;
    krok kr;
    reakcja r;
    akcja a;
    set<big> s;
    set<reakcja,comp> ra;
    set<big>::iterator itz,itd;
    set<reakcja,comp>::iterator it;
    set<akcja,acomp>::iterator ita;
    cin >> n >> m >> k;

    big masa[n+1]; // 0: masa osadu, 1..n: masy substancji
    vector<set<big> > stan; // stan fiolek
    vector<krok> kroki;
    vector<set<reakcja,comp> > reakcje;
    set<akcja,acomp> akcje; // reakcje w bierzacym kroku
    
    // masa
    masa[0]=0;
    for (i=1; i<=n; i++) {
        cin >> masa[i];
    }
    // stan
    s.clear();
    stan.push_back(s);
    for (i=1; i<=n; i++) {
        s.clear();
        s.insert(i);
        stan.push_back(s);
    }
    // kroki
    for (i=0; i<m; i++) {
        cin >> kr.z >> kr.d;
        kroki.push_back(kr);
    }
    // reakcje
    ra.clear();
    for (i=0; i<=n; i++) {
        reakcje.push_back(ra);
    }
    for (i=0; i<k; i++) {
        cin >> c >> d;
        r.prio=i;
        r.a=d;
        reakcje[c].insert(r);
        r.a=c;
        reakcje[d].insert(r);
    }
    
    for (i=0; i<m; i++) {
        akcje.clear();
        for (itz=stan[kroki[i].z].begin(); itz!=stan[kroki[i].z].end(); ++itz) {
            for (itd=stan[kroki[i].d].begin(); itd!=stan[kroki[i].d].end(); ++itd) {
                r.prio=0;
                r.a=*itd;
                it=reakcje[*itz].find(r);
                if (it!=reakcje[*itz].end()) {
                    a.prio=it->prio;
                    a.a=*itz;
                    a.b=*itd;
                    akcje.insert(a);
                }
            }
        }
        for (ita=akcje.begin(); ita!=akcje.end(); ++ita) {
            osad =(masa[ita->a]<=masa[ita->b])?masa[ita->a]:masa[ita->b];
            masa[ita->a]-=osad;
            masa[ita->b]-=osad;
            masa[0]+=2*osad;
            if (masa[ita->a]==0) {
                stan[kroki[i].z].erase(ita->a);
            }
            if (masa[ita->b]==0) {
                stan[kroki[i].d].erase(ita->b);
            }
        }
        for (itz=stan[kroki[i].z].begin(); itz!=stan[kroki[i].z].end(); ++itz) {
            stan[kroki[i].d].insert(*itz);
        }
        stan[kroki[i].z].clear();
    }
    
    cout << masa[0] << endl;
    
    return 0;
}