#include <algorithm>
#include <set>
#include <stack>
using namespace std;

const int MaxN = 20000 + 100, MaxM = 60000 * 2 + 100, MaxQ = 3 * 100000 + 100;
stack <int> Value[MaxN];

struct Node {
	int x, y;
} A[MaxM];
int Multi[MaxM];

bool operator < (const Node &a, const Node &b) {
	return a.x < b.x || a.x == b.x && a.y < b.y;
}
bool operator == (const Node &a, const Node &b) {
	return a.x == b.x && a.y == b.y;
}
bool Valid[MaxM];
struct TQuery {
	char type;
	int x, y;
} Query[MaxQ];

int dad[MaxN];
multiset <int> data[MaxN];

int find_set(int u) {
	if (u == dad[u]) return u;
	else return dad[u] = find_set(dad[u]);
}
void union_set(int u, int v) {
	u = find_set(u); v = find_set(v);
	if (u != v) {
		if (data[u].size() < data[v].size()) swap(u, v);
		dad[v] = u;
		data[u].insert(data[v].begin(), data[v].end());
		data[v].clear();
	}
}


int main() {
	int N, M, Q;
	int cnt, i, j, x, y, ti = 0;
	Node tmp;
	multiset <int> ::iterator it;
	double sum, times;
	
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	
	while (scanf("%d%d%d", &N, &M, &Q) == 3) {
		++ ti;
		sum = 0; times = 0;
		for (i = 0; i < N; i ++)
			while (!Value[i].empty()) Value[i].pop();
		for (i = 0; i < N; i ++) {
			scanf("%d", &j);
			Value[i].push(j);
		}
		for (i = 0; i < M; i ++) {
			scanf("%d%d", &x, &y); x --; y --;
			A[i * 2].x = x; A[i * 2].y = y;
			A[i * 2 + 1].x = y; A[i * 2 + 1].y = x;
		}
		M *= 2;
		sort(A, A + M);
		for (i = 0; i < M; i ++) Multi[i] = 0;
		Multi[M - 1] = 1;
		for (i = M - 2; i >= 0; i --)
			if (A[i] == A[i + 1]) Multi[i] = Multi[i + 1] + 1;
			else Multi[i] = 1;
		
		for (i = 0; i < M; i ++) Valid[i] = true;
		for (i = 0; i < Q; i ++) {
			scanf(" %c %d%d", &Query[i].type, &Query[i].x, &Query[i].y);
			if (Query[i].type == 'E') {
				Query[i].x --; Query[i].y --;
				tmp.x = Query[i].x; tmp.y = Query[i].y;
				cnt = lower_bound(A, A + M, tmp) - A;
				Multi[cnt] --;
				swap(tmp.x, tmp.y);
				cnt = lower_bound(A, A + M, tmp) - A;
				Multi[cnt] --;
				if (Multi[cnt] != 0) Query[i].x = -1;
			} else if (Query[i].type == 'U') {
				Query[i].x --;
				Value[Query[i].x].push(Query[i].y);
			} else {
				Query[i].x --;
			}
		}
		
		for (i = 0; i < N; i ++) dad[i] = i;
		for (i = 0; i < N; i ++) {
			data[i].clear();
			data[i].insert(Value[i].top());
		}

		for (i = 0; i < M; i ++)
			if (Multi[i] > 0 && (i == 0 || !(A[i] == A[i - 1])))
				union_set(A[i].x, A[i].y);

		for (i = Q - 1; i >= 0; i --) {
			if (Query[i].type == 'U') {
				x = find_set(Query[i].x);
				data[x].erase(data[x].find(Value[Query[i].x].top()));
				Value[Query[i].x].pop();
				data[x].insert(Value[Query[i].x].top());
			} else if (Query[i].type == 'E') {
				if (Query[i].x != -1) union_set(Query[i].x, Query[i].y);
			} else {
				Query[i].x = find_set(Query[i].x);
				it = data[Query[i].x].lower_bound(Query[i].y);
				if (it != data[Query[i].x].end()) {
					sum += *it;
					//printf("value = %d\n", *it);
				} else {
					//printf("value = %d\n", 0);
				}
				times = times + 1;
			}
		}
		printf("Case %d: %.3lf\n", ti, sum / times);
	}
	return 0;
}

• 郁闷了，最后不到一个小时就是想这么写，结果比赛完了还没有过样例...... (0) qiqilrq 2008-10-18 20:25:27
  • 这有什么好郁闷的， 写完了没交上去才叫郁闷。。。 (0) chaeyeon 2008-10-18 22:13:30