Submission #660380

#	Time	Username	Problem	Language	Result	Execution time	Memory
660380		GusterGoose27	Bridges (APIO19_bridges)	C++11	73 / 100	3019 ms	12612 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 50000;
const int MAXM = 1e5;
int n, m, q;

class edge {
public:
	int x, y, w;
	edge() {}
	edge(int x, int y, int w) : x(x), y(y), w(w) {}
};

class update {
public:
	bool type; // 0 = update, 1 = query
	int a, b; // two variables
	update() {}
	update(bool t, int a, int b) : type(t), a(a), b(b) {}
};

class query {
public:
	int s, w, i;
	query(int s, int w, int i) : s(s), w(w), i(i) {}
};

bool operator<(query &a, query &b) {
	return (a.w > b.w);
}

bool operator<(edge &a, edge &b) {
	return (a.w == b.w) ? ((a.x == b.x) ? (a.y < b.y) : (a.x < b.x)) : (a.w > b.w);
}

edge edge_list[MAXM];

struct comp {
	bool operator()(const int &a, const int &b) const {
		return (edge_list[a].w == edge_list[b].w) ? (a < b) : (edge_list[a].w > edge_list[b].w);
		// return edge_list[a] < edge_list[b];
	}
};

set<int, comp> edges;
int adj_w[MAXM];
bool vis[MAXN];
vector<int> un_vis;
vector<int> uf_edges[MAXN];
int uf[MAXN];
int rnk[MAXN];
int sz[MAXN];
int block_sz;
int block_cnt;
update updates[MAXM];
int ans[MAXM];

int find(int i) {
	return (uf[i] == -1) ? i : (uf[i] = find(uf[i]));
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) {
		if (rnk[a] < rnk[b]) swap(a, b);
		uf[b] = a;
		sz[a] += sz[b];
		if (rnk[a] == rnk[b]) rnk[a]++;
	}
}

int dfs(int cur) {
	vis[cur] = 1;
	un_vis.push_back(cur);
	int s = sz[cur];
	for (int nxt: uf_edges[cur]) {
		if (!vis[nxt]) s += dfs(nxt);
	}
	return s;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y, w; cin >> x >> y >> w;
		x--; y--;
		edge_list[i] = edge(x, y, w);
		edges.insert(i);
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		int t; int a, b;
		cin >> t >> a >> b;
		a--;
		updates[i] = update(t-1, a, b);
	}
	block_sz = 1+(int)sqrt(q);
	block_cnt = (q+block_sz-1)/(block_sz);
	assert(block_sz*block_cnt >= q);
	for (int i = 0; i < block_cnt; i++) {
		fill(uf, uf+n, -1);
		fill(sz, sz+n, 1);
		memset(rnk, 0, sizeof(int)*n);
		int s = block_sz*i;
		int e = min(block_sz*(i+1), q);
		vector<query> queries; // weight, start
		vector<int> ext_edges;
		for (int j = s; j < e; j++) {
			if (updates[j].type) queries.push_back(query(updates[j].a, updates[j].b, j));
			else {
				if (edges.find(updates[j].a) != edges.end()) {
					ext_edges.push_back(updates[j].a);
					edges.erase(updates[j].a);
				}
			}
		}
		sort(queries.begin(), queries.end());
		auto e_pos = edges.begin();
		for (query p: queries) {
			while (e_pos != edges.end() && edge_list[*e_pos].w >= p.w) {
				merge(edge_list[*e_pos].x, edge_list[*e_pos].y);
				e_pos++;
			}
			for (int v: ext_edges) {
				adj_w[v] = edge_list[v].w;
			}
			for (int j = s; j < p.i; j++) {
				if (updates[j].type) continue;
				adj_w[updates[j].a] = updates[j].b;
			}
			for (int v: ext_edges) {
				if (adj_w[v] >= p.w) {
					int x = find(edge_list[v].x);
					int y = find(edge_list[v].y);
					uf_edges[x].push_back(y);
					uf_edges[y].push_back(x);
				}
			}
			ans[p.i] = dfs(find(p.s));
			for (int v: ext_edges) {
				if (adj_w[v] >= p.w) {
					int x = find(edge_list[v].x);
					int y = find(edge_list[v].y);
					uf_edges[x].clear();
					uf_edges[y].clear();
				}
			}
			for (int v: un_vis) vis[v] = 0;
			un_vis.clear();
		}
		for (int j = e-1; j >= s; j--) {
			if (!updates[j].type && edges.find(updates[j].a) == edges.end()) {
				edge_list[updates[j].a].w = updates[j].b;
				edges.insert(updates[j].a);
			}
		}
	}
	for (int i = 0; i < q; i++) {
		if (updates[i].type) {
			cout << ans[i] << "\n";
			assert(ans[i] != 0);
		}
	}
}

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27