| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 888503 | rukashii | Bridges (APIO19_bridges) | C++17 | 0 ms | 0 KiB |
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>
using namespace std;
#define file if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
#define int long long
#define f first
#define s second
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
if (s.size()) setIn(s+".inp"), setOut(s+".out");
}
const int allmaxn = 5e4 + 2, allmaxm = 1e5 + 2;
int n, m, q;
vector <pair <int, int>> adj[allmaxn];
tuple <int, int, int> edges[allmaxm], Q[allmaxm];
namespace Sub1
{
const int s1maxn = 1002;
multiset <pair <int, int>> msadj[s1maxn];
bool vis[s1maxn];
bool Check()
{
return (n <= 1000 && m <= 1000 && q <= 10000);
}
void solve()
{
for (int i = 1; i <= n; i++)
{
for (auto [v, w] : adj[i])
{
msadj[i].insert({v, w});
}
}
for (int i = 1; i <= q; i++)
{
auto [type, fi, se] = Q[i];
if (type == 1)
{
int b = fi, r = se;
auto [u, v, w] = edges[fi];
msadj[u].erase(msadj[u].find({v, w}));
msadj[v].erase(msadj[v].find({u, w}));
msadj[u].insert({v, r});
msadj[v].insert({u, r});
edges[fi] = {u, v, r};
}
else
{
int st = fi, mxw = se;
memset(vis, 0, sizeof(vis));
queue <int> q;
q.push(st);
vis[st] = 1;
int ans = 1;
while (q.size())
{
int u = q.front();
q.pop();
for (auto [v, w] : msadj[u])
{
if (w >= mxw && !vis[v])
{
vis[v] = 1;
q.push(v);
ans++;
}
}
}
cout << ans << '\n';
}
}
}
} // namespace Sub1
namespace Sub2
{
bool Check()
{
if (m != n - 1)
return 0;
for (int i = 1; i <= m; i++)
{
auto [u, v, w] = edges[i];
if (u != v - 1)
return 0;
}
return 1;
}
const int s2maxn = allmaxn;
int tree[s2maxn * 4 + 10];
int a[s2maxn + 10];
void update(int id, int l, int r, int pl, int val)
{
if (pl > r || pl < l)
return;
if (l == r)
{
tree[id] = val;
return;
}
int mid = (l + r) / 2;
update(id * 2, l, mid, pl, val);
update(id * 2 + 1, mid + 1, r, pl, val);
tree[id] = min(tree[id * 2], tree[id * 2 + 1]);
}
int getL(int id, int l, int r, int v, int val)
{
if (l > v)
assert(0);
if (r <= v)
{
int best = n + 1;
while (1)
{
int L = id * 2, R = id * 2 + 1;
int mid = (l + r) / 2;
if (l == r)
return (a[l] >= val ? l : best);
if (tree[R] >= val)
{
best = mid + 1;
r = mid;
id = L;
}
else
{
l = mid + 1;
id = R;
}
}
}
int mid = (l + r) / 2;
int L = id * 2, R = id * 2 + 1;
if (v <= mid)
return getL(L, l, mid, v, val); // ans must be in the left
if (getL(R, mid + 1, r, v, val) > mid + 1) // if there's an answer int the right
return getL(R, mid + 1, r, v, val);
return min(mid + 1, getL(L, l, mid, v, val));
}
int getR(int id, int l, int r, int u, int val)
{
if (r < u)
return -1;
if (l >= u)
{
int best = -1;
while (1)
{
int L = id * 2, R = id * 2 + 1, mid = (l + r) / 2;
if (l == r)
return (tree[id] >= val ? l : best);
if (tree[L] >= val)
{
best = mid;
l = mid + 1;
id = id * 2 + 1;
}
else
{
r = mid;
id = id * 2;
}
}
}
int mid = (l + r) / 2;
int L = id * 2, R = id * 2 + 1;
if (mid + 1 <= u)
return getR(R, mid + 1, r, u, val);
int tmp = getR(L, l, mid, u, val);
if (tmp < mid)
return tmp;
return max(tmp, getR(R, mid + 1, r, u, val));
}
void solve()
{
// assert(0);
for (int i = 1; i <= m; i++)
{
a[i] = get <2> (edges[i]);
update(1, 1, n, i, a[i]);
}
for (int i = 1; i <= q; i++)
{
auto [type, fi, se] = Q[i];
if (type == 1)
{
a[fi] = se;
update(1, 1, n, fi, se);
}
else
{
int Lbor = fi, Rbor = fi;
if (fi > 1)
{
Lbor = min(getL(1, 1, n, fi - 1, se), Lbor);
}
if (fi < n)
{
Rbor = max(getR(1, 1, n, fi, se) + 1, Rbor);
}
// cout << Lbor << ' ' << Rbor << '\n';
cout << Rbor - Lbor + 1 << '\n';
}
}
}
} // namespace Sub2
namespace Sub3
{
bool Check()
{
for (int i = 1; i <= q; i++)
if (get <0> (Q[i]) == 1)
return 0;
return 1;
}
const int s3maxn = allmaxn, s3maxq = allmaxm;
int lab[s3maxn], sz[s3maxn], ans[s3maxq];
tuple <int, int, int> queries[s3maxq];
int get(int u)
{
return (lab[u] == -1) ? u : (lab[u] = get(lab[u]));
}
void merge(int u, int v)
{
int uu = get(u), vv = get(v);
if (uu == vv)
return;
sz[uu] += sz[vv];
sz[vv] = 0;
lab[v] = u;
}
bool cmp(const tuple <int, int, int> &a, const tuple <int, int, int> &b)
{
auto [u1, v1, w1] = a;
auto [u2, v2, w2] = b;
return (w1 > w2);
}
void solve()
{
assert(0);
for (int i = 1; i <= q; i++)
{
auto [t, s, w] = Q[i];
queries[i] = {w, s, i};
}
sort(queries + 1, queries + 1 + q);
sort(edges + 1, edges + 1 + m, cmp);
reverse(queries + 1, queries + 1 + q);
for (int i = 1; i <= n; i++)
lab[i] = -1, sz[i] = 1;
int pt = 1;
for (int i = 1; i <= q; i++)
{
auto [qw, qs, qid] = queries[i];
if (get<2>(edges[pt]) >= qw)
for (; pt <= m; pt++)
{
auto [u, v, w] = edges[pt];
if (w >= qw)
merge(u, v);
else
break;
}
ans[qid] = sz[get(qs)];
}
for (int i = 1; i <= q; i++)
cout << ans[i] << '\n';
}
} // namespace Sub3
signed main()
{
// setIO();
file;
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
edges[i] = {u, v, w};
}
cin >> q;
for (int i = 1; i <= q; i++)
{
int type, fi, se;
cin >> type >> fi >> se;
Q[i] = {type, fi, se};
}
// if (Sub1::Check()) return Sub1::solve(), 0;
// if (Sub2::Check()) return Sub2::solve(), 0;
if (Sub3::Check()) return Sub3::solve(), 0;
}