이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using pii = pair<int, int>;
const int N = 1e5 + 5, SQRT = 256;
struct Query {
int idx, nod, val, ans;
};
int setval[N], far[N], val[N], cap1[N], cap2[N], bagat[N];
int tip[N], siz[N];
pii qval[N];
vector<pii> undo_stack;
int n, m, q, val_bnd;
static int uget_far(int nod) {
return far[nod] ? uget_far(far[nod]) : nod;
}
static void ujoin(int a, int b) {
a = uget_far(a);
b = uget_far(b);
if (a == b)
return;
if (rand() % 2)
swap(a, b);
far[a] = b;
siz[b]+= siz[a];
undo_stack.emplace_back(a, b);
}
static void undo() {
reverse(begin(undo_stack), end(undo_stack));
for (auto i: undo_stack) {
far[i.x] = 0;
siz[i.y]-= siz[i.x];
}
undo_stack.clear();
}
static int get_far(int nod) {
return far[nod] ? (far[nod] = get_far(far[nod])) : nod;
}
static void join(int a, int b) {
a = get_far(a);
b = get_far(b);
if (a == b)
return;
if (rand() % 2)
swap(a, b);
far[a] = b;
siz[b]+= siz[a];
}
int main() {
#ifdef HOME
freopen("bridges.in", "r", stdin);
freopen("bridges.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
vector<Query> qs;
vector<pii> back_update;
cin >> n >> m;
for (int i = 1; i <= m; ++i)
cin >> cap1[i] >> cap2[i] >> setval[i];
cin >> q;
for (int i = 0; i < q; ++i) {
cin >> tip[i];
if (tip[i] == 1) // [1 - update, 2 - query]
cin >> qval[i].x >> qval[i].y;
else
cin >> qval[i].x >> qval[i].y;
}
qs.reserve(SQRT);
back_update.reserve(N);
for (int start = 0; start < q; start+= SQRT) {
int halt = min(q - 1, start + SQRT - 1);
int back_ptr = 0;
back_update.clear();
qs.clear();
// culege query-uri si seteaza ce nu e de bagat in back
memset(bagat, 0x00, sizeof bagat);
for (int i = start; i <= halt; ++i)
if (tip[i] == 1)
bagat[qval[i].x] = true;
else
qs.push_back({i, qval[i].x, qval[i].y, 0});
// umple back_update si seteaza (back) val
for (int i = start - 1; i >= 0; --i) if (tip[i] == 1 && !bagat[qval[i].x]) {
bagat[qval[i].x] = true;
back_update.emplace_back(qval[i].x, qval[i].y);
}
for (int i = 1; i <= m; ++i) if (!bagat[i]) {
back_update.emplace_back(i, setval[i]);
bagat[i] = true;
}
for (int i = start; i <= halt; ++i)
if (tip[i] == 1)
bagat[qval[i].x] = false;
for (int i = 1; i <= m; ++i)
val[i] = setval[i];
for (int i = 0; i < start; ++i) if (tip[i] == 1)
val[qval[i].x] = qval[i].y;
sort(begin(back_update), end(back_update), [&](const pii &a, const pii &b) {
return a.y > b.y;
});
// set the stage
memset(far, 0x00, sizeof far);
for (int i = 1; i <= n; ++i)
siz[i] = 1;
sort(begin(qs), end(qs), [&](const Query &a, const Query &b) { return a.val > b.val; });
for (auto &q: qs) {
while (back_ptr < int(back_update.size()) && back_update[back_ptr].y >= q.val) {
join(cap1[back_update[back_ptr].x], cap2[back_update[back_ptr].x]);
back_ptr+= 1;
}
for (int i = q.idx; i >= start; --i) if (tip[i] == 1 && !bagat[qval[i].x]) {
bagat[qval[i].x] = 2;
if (qval[i].y < q.val)
continue;
ujoin(cap1[qval[i].x], cap2[qval[i].x]);
}
for (int i = q.idx + 1; i <= halt; ++i) if (tip[i] == 1 && !bagat[qval[i].x]) {
bagat[qval[i].x] = 2;
if (val[qval[i].x] < q.val)
continue;
ujoin(cap1[qval[i].x], cap2[qval[i].x]);
}
q.ans = siz[uget_far(q.nod)];
// cleanup
undo();
for (int i = start; i <= halt; ++i) if (tip[i] == 1)
bagat[qval[i].x] = 0;
}
sort(begin(qs), end(qs), [&](const Query &a, const Query &b) { return a.idx < b.idx;});
for (auto q: qs)
cout << q.ans << '\n';
}
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... |