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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include<stdio.h>
#include<stdlib.h>
#include<vector>


#ifdef DEBUG
#define log(...) fprintf(stderr, __VA_ARGS__ )
#else
#define log(...)
#endif

using namespace std;

struct Mix;

struct Fio {
	int index;		// index fiolki/substancji
	int vol;		// ilość danej substancji

	int mixs;		// ilość miksów związanych z tą substancją
	Mix** mix;		// substancje z którymi ta substancja reaguje

	// dane dla obsługi grup
	int group;		// identyfikator pierwszego elmentu z grupy - początkowo index fiolki
	int groupSize;		// ilość substancji w danej grupie (tylko główny element grupy ma to poprawnie ustawione)
	int groupSteps;		// liczba kroków, które są w danej grupie (tylko główny element grupy ma to poprawnie ustawione)
	Fio*	next;	// fiolka z którą połączono (tworzy listę)
	
	void init(int i) {
		scanf("%d",&vol);
		index=i;
		mixs=0; mix=NULL;
		group=i; groupSize=1; groupSteps=0;
		next=NULL;
	}
	
	void allocMem() {
		mix=(Mix**)malloc(sizeof(Mix*)*groupSteps);
	}
	void add(Mix* m) {
		mix[mixs++]=m;
	}
};

struct Mix {
	int a,b;
	int order;
	
	void init(int i) {
		scanf("%d %d",&a,&b);
		order=i;
	}
	
	/** Metoda zwracająca drugi element do reakcji */
	inline int get(int v) { return (a==v)?b:a; }
};

int mixSort(const void* v1, const void* v2) {
	const Mix* m1=*((const Mix**)v1);
	const Mix* m2=*((const Mix**)v2);
	return m1->order - m2->order;
}

struct Step {
	int v1,v2;
	
	void init() {
		scanf("%d %d",&v1,&v2);
	}
};

int n,m,k;
Fio* fio;
Mix* mix;
Step* step;
int64_t res=0;
vector<Mix*> job;

inline int min(int a, int b) { return a<b?a:b; }

void process(int a, int b) {
	Fio* fa=&fio[a];
	Fio* fb=&fio[b];
	log("Processing A=%d(%d,%d,%d), B=%d(%d,%d,%d)\n",a,fa->group,fa->groupSize,fa->groupSteps,
		b,fb->group, fb->groupSize, fb->groupSteps);
	fa=&fio[fa->group];	// przechodzimy na początek grupy
	fb=&fio[fb->group];
	if((fa->groupSteps*2 + fa->groupSize) < (fb->groupSteps*2 + fb->groupSize)) {
		Fio* tmp=fa; fa=fb; fb=tmp;		// zamieniamy kolejność, tak, że grupa FB ma mniej zadań do wykonania
	}
	log("Connecting groups %d + %d\n",fa->group,fb->group);
	// dodajemy grupy
	int grp=fa->group;
	fa->groupSize+=fb->groupSize;
	fa->groupSteps+=fb->groupSteps;
	
	// wkonujemy prace dla elementów z FB
	Fio* step=fb;
	for(;;) {
		step->group=grp;	// aktualizujemy identyfikator grupy
		if((step->vol>0)&&(step->mixs>0)) {	// jeżeli coś jest...
			for(int i=0;i<step->mixs;++i) {	// dodajemy mixy, które trzeba wykonać
				Mix* m=step->mix[i];
				int re=m->get(step->index);
				if(fio[re].group==grp) {	// jest w nowej mieszance, usuwamy z listy mixow
					step->mixs--;
					if(i<step->mixs) step->mix[i]=step->mix[step->mixs];
					--i;
					--fa->groupSteps;
					if(fio[re].vol>0) job.push_back(m);	// jeżeli jest jakaś zawartość drugiej substancji
				}
			}
		}
	
		if(step->next==NULL) break;
		step=step->next;	// przechodzimy do kolejnego elementu
	}
	// łączymy listy
	step->next=fa->next;	// na końcu FB dodajemy to co jest podpięte do FA
	fa->next=fb;			// do FA podpinamy FB (początek)
	// jeżel są jakieś zadania do wykonia, to je wykonujemy
	if(job.size()>0) {
		// jeżeli jest kilka zadań, to wykonujemy zgodnie z kolejnością
		if(job.size()>1) qsort(job.data(),job.size(),sizeof(Mix*),mixSort);
		for(int i=0;i<job.size();++i) {
			Mix* m=job[i];
			Fio* f1=&fio[m->a];
			Fio* f2=&fio[m->b];
			int s=min(f1->vol,f2->vol);
			log("Processing mix: A %d(%d) + B %d(%d) for %d\n",f1->index,f1->vol, f2->index, f2->vol, s);
			if(s==0) continue;	// już nie ma substancji, więc nie ma połączenia
			f1->vol-=s; f2->vol-=s;
			res+=s*2;
			if(f1->vol==0) {	// skończyła się substancja, to aktualizujemy ilości
				fa->groupSteps-=f1->mixs;	// zmniejszamy ilość mixów, bo juz ich nie będziemy wykonywać 
			}
			if(f2->vol==0) {
				fa->groupSteps-=f2->mixs;
			}
		}
		job.resize(0);
	}
}

int main() {
	scanf("%d %d %d",&n,&m,&k);
	
	fio=(Fio*)malloc(sizeof(Fio)*(n+1));	// 0..n
	mix=(Mix*)malloc(sizeof(Mix)*k);		// 0..k-1
	step=(Step*)malloc(sizeof(Step)*m);		// 0..m-1
	
	log("Loading %d fio, %d mix, %d steps\n",n,k,m);
	
	for(int i=1;i<=n;++i) fio[i].init(i);	// 1..n
	for(int i=0;i<m;++i) step[i].init();	// 0..m
	// odczytanie i zliczenie wystąpień
	for(int i=0;i<k;++i) {					// 0..k-1
		Mix* x=&mix[i];
		x->init(i);
#ifdef DEBUG
		if(x->a==x->b) log("Invalid\n");
#endif
		fio[x->a].groupSteps++;
		fio[x->b].groupSteps++;
	}
	// zainicjowanie pamięci do wystąpień
	for(int i=1;i<=n;++i) fio[i].allocMem();	// 1..n
	// wrzucenie do par reakcji do struktur substancji
	for(int i=0;i<k;++i) {					// 0..k-1
		Mix* x=&mix[i];
		fio[x->a].add(x);
		fio[x->b].add(x);
	}
	// wykonywanie operacji
	for(int i=0;i<m;++i) {					// 0..m-1
		process(step[i].v1,step[i].v2);
	}
	
	printf("%lld\n",res);
	
	return 0;
}