이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "
const ll mod = 1e9 + 7;
const int maxn = 5e4 + 3;
const int INF = 1e9;
const int block = 1000;
struct Edge {
int u, v, w;
Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w) {}
} edges[2 * maxn];
struct Query {
int t, x, y;
Query(int t = 0, int x = 0, int y = 0): t(t), x(x), y(y) {}
} quy[2 * maxn];
int n, m, q, res[2 * maxn];
stack<int> st;
bool bad[2 * maxn];
vector<int> upd[2 * maxn], change, unchange, ask;
struct DisjointSet {
int par[maxn], Rank[maxn];
int find(int x) {
while (x != par[x]) x = par[x];
return x;
}
bool join(int u, int v) {
u = find(u); v = find(v);
if (u == v) return 0;
if (Rank[u] < Rank[v])
swap(u, v);
st.push(v);
Rank[u] += Rank[v];
par[v] = u;
return 1;
}
void rollback(int x) {
while ((int)st.size() > x) {
int u = st.top(); st.pop();
Rank[par[u]] -= Rank[u];
par[u] = u;
}
}
} Dsu;
void reset() {
for (int i = 1; i <= n; i++) {
Dsu.par[i] = i; Dsu.Rank[i] = 1;
}
for (int i = 1; i <= m; i++)
bad[i] = false;
vector<int>().swap(change);
vector<int>().swap(unchange);
vector<int>().swap(ask);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen(".INP", "r", stdin);
//freopen(".OUT", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, w; cin >> u >> v >> w;
edges[i] = {u, v, w};
}
cin >> q;
for (int i = 1; i <= q; i++) {
int t, x, y; cin >> t >> x >> y;
quy[i] = {t, x, y};
}
for (int l = 1; l <= q; l += block) {
int r = min(l + block - 1, q);
reset();
for (int i = l; i <= r; i++)
if (quy[i].t == 1)
bad[quy[i].x] = true;
for (int i = 1; i <= m; i++)
if (!bad[i]) unchange.pb(i);
else change.pb(i);
for (int i = l; i <= r; i++) {
if (quy[i].t == 1)
edges[quy[i].x].w = quy[i].y;
else {
ask.pb(i);
vector<int>().swap(upd[i]);
for (auto k : change)
if (edges[k].w >= quy[i].y)
upd[i].pb(k);
}
}
sort(unchange.begin(), unchange.end(),[&] (int i, int j) {
return edges[i].w > edges[j].w;
});
sort(ask.begin(), ask.end(),[&](int i, int j) {
return quy[i].y > quy[j].y;
});
int pos = 0;
for (int i : ask) {
while (pos < (int)unchange.size() && quy[i].y <= edges[unchange[pos]].w) {
Dsu.join(edges[unchange[pos]].u, edges[unchange[pos]].v);
pos++;
}
int sz = st.size();
for (int k : upd[i])
Dsu.join(edges[k].u, edges[k].v);
quy[i].x = Dsu.find(quy[i].x);
res[i] = Dsu.Rank[quy[i].x];
Dsu.rollback(sz);
}
}
for (int i = 1; i <= q; i++)
if (res[i]) cout << res[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... |