이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
using namespace std;
const long long INF = 1ll << 60;
const int N = 1e5 + 5;
int dpr[N];
vector<array<int, 3>> undo;
int gpr(int x) {
while (dpr[x] >= 0) x = dpr[x];
return x;
}
bool merge(int u, int v) {
u = gpr(u), v = gpr(v);
if (u == v) return false;
if (dpr[u] > dpr[v]) swap(u, v); //v is bigger now
undo.push_back({u, v, dpr[u]});
dpr[v] += dpr[u];
dpr[u] = v;
return true;
}
void rollback() {
auto a = undo.back();
undo.pop_back();
int u = a[0], v = a[1], lst = a[2];
dpr[u] = lst;
dpr[v] -= lst;
return;
}
const int SQ = 350;
const int SQ2 = N / SQ + 5;
int a[N], b[N], U[N], W[N], V[N], n, m, q, ans[N];
short t[N];
void solve() {
//t = 1 CHANGE
//t = 2 SOAL
FOR(i, 0, SQ2) {
int L = i * SQ, R = min(q, (i + 1) * SQ);
if (L >= q) break;
memset(dpr, -1, sizeof dpr);
undo.clear();
bitset<N> change = 0, mark = 0;
vector<int> Q, E, NE;
FOR(j, L, R) {
if (t[j] == 1) change[a[j]] = true;
else Q.push_back(j);
}
FOR(j, 0, m) (change[j] ? NE : E).push_back(j);
sort(E.rbegin(), E.rend(), [&](const int x, const int y) {return W[x] < W[y];});
sort(Q.begin(), Q.end(), [&](const int x, const int y) {return b[x] < b[y];});
for (auto qid: Q) {
while (E.size() && W[E.back()] <= b[qid]) {
merge(U[E.back()], V[E.back()]);
E.pop_back();
}
int cnt = 0;
for (int j = qid; j >= L; j--) if (t[j] == 1 && !mark[a[j]]) {
if (b[j] <= b[qid]) {
cnt += merge(U[a[j]], V[a[j]]);
mark[a[j]] = true;
}
mark[a[j]] = true;
}
for (auto e: NE) if (!mark[e]) {
mark[e] = true;
if (W[e] <= b[qid]) {
cnt += merge(U[e], V[e]);
mark[e] = true;
}
}
ans[qid] = dpr[gpr(a[qid])];
while (cnt--) rollback();
FOR(j, L, qid) mark[a[j]] = false;
for (auto e: NE) mark[e] = false;
}
FOR(j, L, R) if (t[j] == 1) W[a[j]] = b[j];
}
FOR(i, 0, q) if (t[i] == 2) cout << -ans[i] << '\n';
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
FOR(i, 0, m) {
cin >> U[i] >> V[i] >> W[i];
U[i]--, V[i]--;
W[i] = -W[i];
}
cin >> q;
FOR(i, 0, q) {
cin >> t[i] >> a[i] >> b[i];
a[i]--;
b[i] = -b[i];
}
solve();
return 0;
}
# | 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... |