This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Source: https://oj.uz/problem/view/APIO19_bridges
//
#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<int> vi;
#define FOR(i, a, b) for (int i = (a); i<b; i++)
bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }
bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }
const int Q = 1e5 + 10;
const int N = 5e4 + 10;
const int B = Q;
int t[Q], x[Q], y[Q];
int a[Q], b[Q], w[Q];
stack<vi> ops;
vi p(N, -1);
int res[Q];
int get(int cur) {
return p[cur] < 0 ? cur : get(p[cur]);
}
void unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) return;
if (-p[x] < -p[y]) swap(x, y);
ops.push({y, p[y], x});
p[x] += p[y];
p[y] = x;
// cout << ' ' << x << p[x] << endl;
}
void rollback() {
while (!ops.empty()) {
vi cur = ops.top();
ops.pop();
p[cur[0]] = cur[1];
p[cur[2]] -= cur[1];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
FOR(i, 1, m + 1) {
cin >> a[i] >> b[i] >> w[i];
}
int q;
cin >> q;
FOR(i, 1, q + 1) cin >> t[i] >> x[i] >> y[i];
for (int l = 1; l <= q; l += B) {
// cout << l << endl;
int r = min(l + B, q);
vector<bool> changed(m + 1, false);
vpii unchanged;
vector<vi> add(r - l + 1);
vpii query;
for (int i = l; i <= r; i++) {
if (t[i] == 1) {
w[x[i]] = y[i]; // set the new weight
changed[x[i]]=true;
} else {
for (int j = l; j <= r; j++) {
if (t[j] == 1 && w[x[j]] >= y[i]) {
// cout << ' ' << i << x[j] << endl;
add[i - l].pb(x[j]); // add this new update if we can cross this bridge
}
}
query.pb({y[i], i});
}
}
FOR(i, 1, m + 1) if (!changed[i]) {
unchanged.pb({w[i], i});
}
// cout << unchanged.size() << endl;
sort(unchanged.rbegin(), unchanged.rend());
sort(query.rbegin(), query.rend());
int un_ind = 0;
for (auto ask: query) {
while (un_ind != unchanged.size() && unchanged[un_ind].f >= y[ask.s]) {
// cout << ask.s << unchanged[un_ind].s << endl;
unite(a[unchanged[un_ind].s], b[unchanged[un_ind].s]);
un_ind++;
}
while (!ops.empty()) ops.pop();
for (auto merge: add[ask.s - l]) {
// cout << ask.s << merge << endl;
unite(a[merge], b[merge]);
}
// cout << ask.s << -p[get(x[ask.s])] << endl;
res[ask.s] = -p[get(x[ask.s])];
rollback();
}
}
FOR(i, 1, q + 1) {
if (t[i] == 2) {
// cout << i << endl;
cout << res[i] << endl;
}
}
}
Compilation message (stderr)
bridges.cpp: In function 'int main()':
bridges.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | while (un_ind != unchanged.size() && unchanged[un_ind].f >= y[ask.s]) {
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
# | 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... |