| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 336353 | 12tqian | Bridges (APIO19_bridges) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
struct DSU {
std::vector<int> e;
void init(int n) {
e = std::vector<int>(n, -1);
}
int get(int x) {
return e[x] < 0 ? x : e[x] = get(e[x]);
}
bool same_set(int a, int b) {
return get(a) == get(b);
}
int size(int x) {
return -e[get(x)];
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) return false;
if (e[x] > e[y]) std::swap(x, y);
e[x] += e[y]; e[y] = x;
return true;
}
};
inline char gc() { // like getchar()
static char buf[1 << 16];
static size_t bc, be;
if (bc >= be) {
buf[0] = 0, bc = 0;
be = fread(buf, 1, sizeof(buf), stdin);
}
return buf[bc++]; // returns 0 on EOF
}
int read_int() {
int a, c;
while ((a = gc()) < 40);
if (a == '-') return -read_int();
while ((c = gc()) >= 48) a = a * 10 + c - 480;
return a - 48;
}
int main() {
const int B = 800;
using namespace std;
int n = read_int();
int m = read_int();
vector<vector<int>> adj(n);
vector<array<int, 3>> ed;
set<array<int, 2>> use;
for (int i = 0; i < m; i++) {
int u = read_int();
int v = read_int();
int w = read_int();
u--, v--;
use.emplace(w, i);
ed.push_back({u, v, w});
}
vector<array<int, 3>> modify;
vector<array<int, 3>> queries;
vector<array<int, 2>> ans;
vector<int> vis(n);
vector<int> mod(m);
vector<int> change(m, -1);
vector<int> rem;
vector<int> todo;
DSU D;
int q = read_int();
for (int i = 0; i < q; i++) {
int x = read_int();
int y = read_int();
int z = read_int();
y--;
if (x == 1)
modify.push_back({y, z, i});
else
queries.push_back({y, z, i});
if (i == q - 1 || int(modify.size()) + int(queries.size()) == B) {
sort(queries.begin(), queries.end(), [](array<int, 3>& a, array<int, 3>& b) {
return a[1] > b[1];
});
D.init(n);
for (auto& mm : modify)
mod[mm[0]] = 1;
auto it = use.end();
for (auto& qq : queries) {
int weight = qq[1];
int ti = qq[2];
if (it == use.begin()) break;
auto ii = (*it)[1];
while (it != use.begin() && ed[ii][2] >= weight) {
it--;
if (!mod[ii])
D.unite(ed[ii][0], ed[ii][1]);
}
for (auto& mm : modify) {
todo.push_back(mm[0]);
if (mm[2] < ti)
change[mm[0]] = mm[1];
}
for (auto& t : todo) {
if (change[t] == -1) {
if (ed[t][2] >= weight) {
int u = D.get(ed[t][0]);
int v = D.get(ed[t][1]);
adj[u].push_back(v);
adj[v].push_back(u);
}
} else {
if (change[t] >= weight) {
int u = D.get(ed[t][0]);
int v = D.get(ed[t][1]);
adj[u].push_back(v);
adj[v].push_back(u);
}
}
}
int res = 0;
function<void(int)> dfs = [&](int src) {
vis[src] = 1;
res += D.size(src);
rem.push_back(src);
for (int nxt : adj[src]) {
if (vis[nxt])
continue;
dfs(nxt);
}
};
dfs(D.get(qq[0]));
ans.push_back({ti, res});
for (auto& r : rem)
vis[r] = 0;
for (auto& t : todo) {
change[t] = -1;
int u = D.get(ed[t][0]);
int v = D.get(ed[t][1]);
adj[u].clear();
adj[v].clear();
}
rem.clear();
todo.clear();
}
for (auto& mm : modify) {
mod[mm[0]] = 0;
use.erase({ed[mm[0]][2], mm[0]});
ed[mm[0]][2] = mm[1];
use.insert({ed[mm[0]][2], mm[0]});
}
queries.clear();
modify.clear();
}
}
sort(ans.begin(), ans.end());
for (auto& a : ans)
cout << a[1] << '\n';
return 0;
}