이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
struct dsu {
vector<pair<int&, int>> undo;
vector<int> par, siz;
dsu(int n) : par(n), siz(n, 1) {
iota(all(par), 0);
}
int find(int u) {
return par[u] == u ? u : find(par[u]);
}
void unite(int u, int v) {
if ((u=find(u)) != (v=find(v))) {
if (siz[u] < siz[v]) swap(u, v);
undo.push_back({siz[u], siz[u]});
undo.push_back({par[v], par[v]});
siz[u] += siz[v];
par[v] = u;
}
}
int snapshot() {
return undo.size();
}
void rollback(int until) {
while (undo.size() > until) {
undo.back().first = undo.back().second;
undo.pop_back();
}
}
};
const int K = 300;
int n, m, q;
vector<array<int, 3>> edges;
vector<int> cur_edge_w;
vector<int> sorted;
void solve() {
cin >> n >> m;
cur_edge_w.resize(m);
for (int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w; u--; v--;
cur_edge_w[i] = w;
edges.push_back({w, u, v});
}
sorted.resize(m); iota(all(sorted), 0);
map<int, int> original_w;
vector<array<int, 3>> events;
auto answer_block = [&]() {
vector<array<int, 3>> extra;
for (auto [edge_ind, w] : original_w) if (w > edges[edge_ind][0]) {
extra.push_back({1, edge_ind, w});
}
events.insert(begin(events), all(extra));
sort(all(sorted), [&](int i, int j) {return edges[i] > edges[j];});
dsu uf(n);
// for (int i = 0; i < m; i++) cerr << edges[sorted[i]][0] << ' ' << edges[sorted[i]][1] <<' ' << edges[sorted[i]][2] << endl;
vector<array<int, 4>> tp2_events; // thres, u, ind, local ind in tp2
for (int i = 0; i < events.size(); i++) {
auto [tp, p1, p2] = events[i];
if (tp == 2) {
tp2_events.push_back({p2, p1, i, (int)tp2_events.size()});
}
}
sort(all(tp2_events));
vector<int> ans(tp2_events.size());
for (int i = 0; i <= m; i++) {
int snap = uf.snapshot();
while (tp2_events.size() && (i == m || tp2_events.back()[0] > edges[sorted[i]][0])) {
auto [THRES, U, IND, TP2_IND] = tp2_events.back(); tp2_events.pop_back();
set<int> new_edges;
for (int j = 0; j < IND; j++) {
auto [tp, p1, p2] = events[j];
if (tp == 2) continue;
if (p2 >= THRES) new_edges.insert(p1);
else if (p2 < THRES && new_edges.count(p1)) new_edges.erase(p1);
}
for (auto edge_ind : new_edges) uf.unite(edges[edge_ind][1], edges[edge_ind][2]);
ans[TP2_IND] = uf.siz[uf.find(U)];
}
uf.rollback(snap);
// if (i < m) cerr << "unite " << edges[sorted[i]][1] << ' ' << edges[sorted[i]][2] << endl;
if (i < m) uf.unite(edges[sorted[i]][1], edges[sorted[i]][2]);
}
for (int i = 0; i < ans.size(); i++) cout << ans[i] << '\n';
events.clear();
for (int i = 0; i < m; i++) edges[i][0] = cur_edge_w[i];
};
cin >> q;
for (int i = 0; i < q; i++) {
if (i > 0 && i % K == 0) answer_block();
int tp; cin >> tp;
if (tp == 1) {
int i, w; cin >> i >> w; i--;
if (!original_w.count(i))
original_w[i] = edges[i][0];
edges[i][0] = min(edges[i][0], w);
cur_edge_w[i] = w;
events.push_back({1, i, w});
} else {
int u, w; cin >> u >> w; u--;
events.push_back({2, u, w});
}
}
answer_block();
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
}
컴파일 시 표준 에러 (stderr) 메시지
bridges.cpp: In member function 'void dsu::rollback(int)':
bridges.cpp:29:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int&, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
29 | while (undo.size() > until) {
| ~~~~~~~~~~~~^~~~~~~
bridges.cpp: In lambda function:
bridges.cpp:65: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]
65 | for (int i = 0; i < events.size(); i++) {
| ~~^~~~~~~~~~~~~~~
bridges.cpp:94:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int i = 0; i < ans.size(); i++) cout << ans[i] << '\n';
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |