제출 #1074819

#제출 시각아이디문제언어결과실행 시간메모리
1074819BuzzyBeez다리 (APIO19_bridges)C++17
0 / 100
3048 ms9532 KiB
#include <bits/stdc++.h>
using namespace std;

tuple<int, int, int> E[100008], Q[100008];
bool mark[100008]; int answer[100008];

struct Disjoint_Set_Union {
	static const int N = 5e4;
	int par[N + 8], sz[N + 8];
	vector<pair<int*, int>> history;
	
	void init(int n) {
		iota(par, par + n + 1, 0);
		fill(sz + 1, sz + n + 1, 1);
		history.clear();
	}
	
	int find(int u) {
		if (par[u] == u) return u;
		return find(par[u]);
	}
	
	void join(int u, int v) {
		u = find(u); v = find(v);
		if (u == v) return;
		if (sz[u] < sz[v]) swap(u, v);
		history.push_back({par + v, par[v]});
		history.push_back({sz + u, sz[u]});
		par[v] = u; sz[u] += sz[v];
	}
	void join(int E_id) {join(get<0>(E[E_id]), get<1>(E[E_id]));}
	
	int current_snapshot() {return history.size();}
	void rollback_to(int ver) {
		while (history.size() > ver) {
			*history.back().first = history.back().second;
			history.pop_back();
		}
	}
	
	int query(int u) {return sz[find(u)];}
} DSU;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m, u, v, w; cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> u >> v >> w;
		E[i] = {u, v, w};
	}
	vector<pair<int, int>> unchanged; vector<tuple<int, int, int>> queried;
	int q, tq, type, id, Qid, nw, tu, tv, tw, cur; cin >> q; int S = sqrt(q);
	for (int i = 1; i <= q; i += S) {
		tq = min(S, q - i + 1); memset(mark, 0, sizeof mark); queried.clear(); unchanged.clear(); DSU.init(n);
		for (int j = i; j < i + tq; ++j) {
			cin >> type >> u >> v;
			Q[j] = {type, u, v};
			if (type == 1) mark[u] = 1;
			else queried.push_back({v, u, j});
		}
		for (int i = 1; i <= m; ++i) if (!mark[i]) unchanged.push_back({get<2>(E[i]), i});
		sort(unchanged.begin(), unchanged.end());
		sort(queried.begin(), queried.end());
		for (tuple<int, int, int> query : queried) {
			tie(w, u, Qid) = query;
			while (!unchanged.empty() && unchanged.back().first >= w) 
				DSU.join(unchanged.back().second), unchanged.pop_back();
			cur = DSU.current_snapshot();
			for (int j = i; j < Qid; ++j) if (get<0>(Q[j]) == 1) {
				tie(type, id, nw) = Q[j]; tie(tu, tv, tw) = E[id];
				E[id] = {tu, tv, nw};
			}
			for (int j = i; j < i + tq; ++j) if (get<0>(Q[j]) == 1) {
				tie(type, id, nw) = Q[j];
				if (get<2>(E[id]) >= w) DSU.join(id);
			}
			answer[Qid] = DSU.query(u);
			DSU.rollback_to(cur);
		}
		for (int j = i; j < i + tq; ++j) if (get<0>(Q[j]) == 1) {
			tie(type, id, nw) = Q[j]; tie(u, v, w) = E[id];
			E[id] = {u, v, nw};
		}
	}
	for (int i = 1; i <= q; ++i) if (answer[i]) cout << answer[i] << '\n';
}

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

bridges.cpp: In member function 'void Disjoint_Set_Union::rollback_to(int)':
bridges.cpp:35:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int*, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |   while (history.size() > ver) {
      |          ~~~~~~~~~~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...