제출 #318072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
318072		kostia244	다리 (APIO19_bridges)	C++17	14 / 100	1446 ms	14360 KiB

bridges

#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int maxn = 100100, B = 401;
int n, m, q, old[maxn], touch[maxn], ans[maxn];
vector<array<int, 4>> edges;
vector<array<int, 2>> weights[maxn];
struct dsu {
	vector<int> r, p, rb;
	dsu(int n = 0) : r(n, 1), p(n) { iota(all(p), 0); }
	int par(int v) {
		if(p[v] == v) return v;
		return par(p[v]);
	}
	void unite(int i, int j) {
		i = par(i), j = par(j);
		rb.push_back(-1);
		if(i == j) return;
		if(r[i] < r[j]) swap(i, j);
		p[j] = i;
		r[i] += r[j];
		rb.push_back(j);
	}
	void roll_back(int c) {
		while(c--) {
			int v = rb.back(); rb.pop_back();
			if(v == -1) continue;
			r[p[v]] -= r[v];
			p[v] = v;
		}
	}
};
int get_weight(int e, int t) {
	int i = weights[e].size()-1;
	while(weights[e][i][0] > t) i--;
	return weights[e][i][1];
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	edges.resize(m);
	int tmp = 1;
	for(auto &[x, y, z, old_id] : edges) {
		cin >> x >> y >> z, x--, y--, old_id = tmp++;
		z *= -1;
	}
	sort(all(edges), [](auto &a, auto &b) { return a[2] < b[2]; });
	tmp = 0;
	for(auto &[x, y, z, old_id] : edges) {
		weights[tmp].push_back({-1, z});
		old[old_id] = tmp++;
	}
	
	memset(ans, -1, sizeof ans);
	cin >> q;
	for(int l = 0; l < q; l+=B) {
		int r = min(q, l+B);
		vector<array<int, 3>> todo;
		vector<int> touched;
		for(int t, a, b, i = l; i < r; i++) {
			cin >> t >> a >> b;
			b *= -1;
			if(t == 1) {
				touch[old[a]] = 1+l;
				weights[old[a]].push_back({i, b});
				touched.push_back(old[a]);
			} else {
				a--;
				todo.push_back({b, a, i});
			}
		}
		sort(all(todo));
		dsu d(n);
		for(int j = 0, I = 0; I < todo.size(); I++) {
			int t = todo[I][2], w = todo[I][0], v = todo[I][1];
			while(j < m) {
				if(touch[j] == 1+l) {j++; continue;}
				if(weights[j].back()[1] > w) break;
				d.unite(edges[j][0], edges[j][1]);
				j++;
			}
			int rb = 0;
			for(auto i : touched) if(get_weight(i, t) <= w) rb++, d.unite(edges[i][0], edges[i][1]);
			ans[t] = d.r[d.par(v)];
			d.roll_back(rb);
		}
	}
	for(int i = 0; i < q; i++) if(ans[i] >= 0) cout << ans[i] << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'int main()':
bridges.cpp:75:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for(int j = 0, I = 0; I < todo.size(); I++) {
      |                         ~~^~~~~~~~~~~~~

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