| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1200305 | trufanov.p | 다리 (APIO19_bridges) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <queue>
#include <unordered_set>
#include <deque>
#include <numeric>
#include <cmath>
#include <unordered_map>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
struct Edge {
int u, v, lim, ind;
Edge(int u, int v, int lim, int ind) :u(u), v(v), lim(lim), ind(ind) {}
bool operator <(const Edge& other) const {
return lim > other.lim;
}
};
struct FirstType {
int t, ind, nlim;
FirstType(int t, int ind, int nlim) :t(t), ind(ind), nlim(nlim) {}
};
struct SecondType {
int t, v, w;
SecondType(int t, int v, int w) :t(t), v(v), w(w) {}
bool operator <(const SecondType& other) const {
return w > other.w;
}
};
enum class Array {
P, D, SZ
};
struct RollBack {
Array arr;
int pos, old;
RollBack(Array arr, int pos, int old) :arr(arr), pos(pos), old(old) {}
};
struct DSU {
vector<int> p, d, sz;
vector<RollBack> rolls;
DSU(int n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
d.resize(n);
sz.resize(n, 1);
}
int get_par(int v) {
if (v == p[v]) {
return v;
}
return get_par(p[v]);
}
void unite(int u, int v, bool save = false) {
u = get_par(u);
v = get_par(v);
if (u != v) {
if (d[u] > d[v]) {
swap(u, v);
}
if (save) {
rolls.push_back(RollBack(Array::P, u, p[u]));
}
p[u] = v;
if (d[u] == d[v]) {
if (save) {
rolls.push_back(RollBack(Array::D, v, d[v]));
}
d[v]++;
}
if (save) {
rolls.push_back(RollBack(Array::SZ, v, sz[v]));
}
sz[v] += sz[u];
}
}
int get_ans(int v) {
return sz[get_par(v)];
}
void rollback() {
for (int i = rolls.size() - 1; i > -1; --i) {
if (rolls[i].arr == Array::P) {
p[rolls[i].pos] = rolls[i].old;
} else if (rolls[i].arr == Array::D) {
d[rolls[i].pos] = rolls[i].old;
} else {
sz[rolls[i].pos] = rolls[i].old;
}
}
rolls.clear();
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<Edge> edges;
for (int i = 0; i < m; ++i) {
int u, v, lim;
cin >> u >> v >> lim;
u--, v--;
edges.push_back(Edge(u, v, lim, i));
}
int q;
cin >> q;
vector<int> ans(q, -1);
int C = (int)sqrt(q);
vector<vector<FirstType>> ft;
vector<vector<SecondType>> st;
for (int i = 0; i < q; ++i) {
if (i / C == ft.size()) {
ft.push_back(vector<FirstType>());
st.push_back(vector<SecondType>());
}
int type;
cin >> type;
if (type == 1) {
int ind, lim;
cin >> ind >> lim;
ind--;
ft[i / C].push_back(FirstType(i, ind, lim));
} else {
int v, w;
cin >> v >> w;
v--;
st[i / C].push_back(SecondType(i, v, w));
}
}
int blocks = ft.size();
for (int b = 0; b < blocks; ++b) {
sort(edges.begin(), edges.end());
vector<int> perm(m);
for (int i = 0; i < m; ++i) {
perm[edges[i].ind] = i;
}
sort(st[b].begin(), st[b].end());
DSU dsu(n);
int it = 0;
unordered_set<int> changed;
for (auto& ftq : ft[b]) {
changed.insert(ftq.ind);
}
for (auto& stq : st[b]) {
while (it < m && edges[it].lim >= stq.w) {
if (!changed.count(edges[it].ind)) {
dsu.unite(edges[it].u, edges[it].v);
}
it++;
}
unordered_map<int, int> last;
for (auto& ftq : ft[b]) {
if (ftq.t < stq.t) {
last[ftq.ind] = ftq.nlim;
} else {
if (edges[perm[ftq.ind]].lim >= stq.w && !last.count(ftq.ind)) {
dsu.unite(edges[perm[ftq.ind]].u, edges[perm[ftq.ind]].v, true);
}
}
}
for (auto& e : last) {
if (e.second >= stq.w) {
dsu.unite(edges[perm[e.first]].u, edges[perm[e.first]].v, true);
}
}
ans[stq.t] = dsu.get_ans(stq.v);
dsu.rollback();
}
for (auto& ftq : ft[b]) {
edges[perm[ftq.ind]].lim = ftq.nlim;
}
}
for (int i = 0; i < q; ++i) {
if (ans[i] != -1) {
cout << ans[i] << '\n';
}
}
}
*/