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>
#define x first
#define y second
using namespace std;
struct ParseIn {
static const int BMAX = 1 << 17;
char buff[BMAX];
int bp;
FILE *fi;
ParseIn(string str) {
fi = fopen(str.c_str(), "r");
bp = BMAX; }
ParseIn() {
fi = stdin;
bp = BMAX; }
char nextch() {
if (bp == BMAX) {
fread(buff, 1, BMAX, fi);
bp = 0;
}
return buff[ bp++ ]; }
ParseIn &operator >> (int &num) {
char ch;
num = 0;
do {
ch = nextch();
}
while (ch < '0' || '9' < ch);
while ('0' <= ch && ch <= '9') {
num = num * 10 + (ch - '0');
ch = nextch();
}
return *this;
}
} fi;
using pii = pair<int, int>;
const int N = 5e4 + 5, M = 1e5 + 5, V = 1e6, SQRT = 320;
struct Query {
int idx, nod, val, ans;
};
vector<pii> bucket[V];
int setval[M], far[N], ufar[N], usiz[N], val[M], cap1[M], cap2[M], bagat[M];
int tip[M], siz[N];
pii qval[M];
vector<int> undo_stack;
int n, m, q, val_bnd;
static void mare_normalizare() {
map<int, int> mp;
for (int i = 1; i <= m; ++i)
mp[setval[i]] = 0;
for (int i = 0; i < q; ++i)
mp[qval[i].y] = 0;
for (auto &i: mp)
i.y = val_bnd++;
for (int i = 1; i <= m; ++i)
setval[i] = mp[setval[i]];
for (int i = 0; i < q; ++i)
qval[i].y = mp[qval[i].y];
}
static void bsort(vector<pii> &upd) {
int bnd = 0;
for (auto i: upd) {
bucket[i.y].push_back(i);
bnd = max(bnd, i.y);
}
upd.clear();
for (int i = bnd; i >= 0; --i) {
for (auto j: bucket[i])
upd.push_back(j);
bucket[i].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];
}
static int uget_far(int nod) {
return ufar[nod] ? (ufar[nod] = uget_far(ufar[nod])) : nod;
}
static void ujoin(int a, int b) {
a = uget_far(get_far(a));
b = uget_far(get_far(b));
if (usiz[a] == 0)
usiz[a] = siz[a];
if (usiz[b] == 0)
usiz[b] = siz[b];
undo_stack.push_back(a);
undo_stack.push_back(b);
if (a == b)
return;
if (rand() % 2)
swap(a, b);
ufar[a] = b;
usiz[b]+= usiz[a];
}
static void undo() {
for (auto i: undo_stack) {
ufar[i] = 0;
usiz[i] = 0;
}
undo_stack.clear();
}
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;
fi >> n >> m;
for (int i = 1; i <= m; ++i)
fi >> cap1[i] >> cap2[i] >> setval[i];
fi >> q;
for (int i = 0; i < q; ++i) {
fi >> tip[i] >> qval[i].x >> qval[i].y;
}
mare_normalizare();
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;
bsort(back_update);
// 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 = max(siz[get_far(q.nod)], usiz[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;
}
Compilation message (stderr)
bridges.cpp: In member function 'char ParseIn::nextch()':
bridges.cpp:22:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fread(buff, 1, BMAX, fi);
~~~~~^~~~~~~~~~~~~~~~~~~
# | 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... |