| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 126713 | roseanne_pcy | Bridges (APIO19_bridges) | C++14 | 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>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 1e5+5;
const int maxs = 325;
const int lim = 320;
int n, m, q;
int a[maxn], b[maxn], w[maxn];
bool chang[maxn];
struct que
{
int t, a, b, id;
bool operator < (que other)
{
return b> other.b;
}
};
que qq[maxn];
const int maxu = 5e4+5;
struct dsu
{
int par[maxu], rnk[maxu], cc[maxu];
stack<hist> roll;
struct hist
{
int u, rnku, ccu, v, rnkv, ccv;
hist(int _u, int _rnku, int _ccu, int _v, int _rnkv, int _ccv)
{
u = _u;
rnku = _rnku;
ccu = _ccu;
v = _v;
rnkv = _rnkv;
ccv = _ccv;
}
while(!roll.empty()) roll.pop_back();
};
dsu(int n = 0)
{
for(int i = 1; i<= n; i++)
{
par[i] = i;
rnk[i] = 0;
cc[i] = 1;
}
}
int findset(int x)
{
if(x == par[x]) return x;
return findset(par[x]);
}
bool unite(int a, int b)
{
int u = findset(a), v = findset(b);
if(u == v) return false;
if(rnk[u]> rnk[v]) swap(u, v);
roll.push(hist(u, rnk[u], cc[u], v, rnk[v], cc[v]));
par[u] = v;
cc[v] += cc[u];
if(rnk[u] == rnk[v]) rnk[v]++;
return true;
}
void rollback()
{
hist k = roll.top(); roll.pop();
par[k.u] = k.u;
rnk[k.u] = k.rnku;
cc[k.u] = k.ccu;
par[k.v] = k.v;
rnk[k.v] = k.rnkv;
cc[k.v] = k.ccv;
}
};
dsu foo;
bool cmp(int a, int b)
{
return w[a]> w[b];
}
bool cmp2(que a, que b)
{
return a.id< b.id;
}
int ans[maxn];
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1; i<= m; i++) scanf("%d %d %d", &a[i], &b[i], &w[i]);
scanf("%d", &q);
for(int i = 1; i<= q; i++)
{
scanf("%d %d %d", &qq[i].t, &qq[i].a, &qq[i].b);
qq[i].id = i;
}
vector<int> edges;
for(int i = 1; i<= m; i++) edges.pb(i);
for(int i = 1; 1+(i-1)*lim<= q; i++)
{
int s = 1+(i-1)*lim;
int t = min(lim*i, q);
memset(chang, 0, sizeof chang);
for(int j = s; j<= t; j++)
{
if(qq[j].t == 1)
{
chang[qq[j].a] = true;
}
}
sort(edges.begin(), edges.end(), cmp);
sort(qq+s, qq+t+1);
int ptr = 0;
foo = dsu(n);
for(int j = s; j<= t; j++)
{
if(qq[j].t == 1) continue;
while(ptr< m && w[edges[ptr]]>= qq[j].b)
{
if(chang[edges[ptr]])
{
ptr++;
continue;
}
foo.unite(a[edges[ptr]], b[edges[ptr]]);
// printf("unite %d %d\n", a[edges[ptr]], b[edges[ptr]]);
ptr++;
}
// printf("answering query %d\n", qq[j].id);
map<int, ii> mod;
for(int k = s; k<= t; k++)
{
if(qq[k].t == 2) continue;
mod[qq[k].a] = {0, w[qq[k].a]};
if(qq[k].id> qq[j].id) continue;
mod[qq[k].a] = max(mod[qq[k].a], {qq[k].id, qq[k].b});
}
int connt = 0;
for(auto kk : mod)
{
if(kk.Y.Y>= qq[j].b)
{
connt += foo.unite(a[kk.X], b[kk.X]);
}
}
ans[qq[j].id] = foo.cc[foo.findset(qq[j].a)];
while(connt--) foo.rollback();
}
sort(qq+s, qq+t+1, cmp2);
for(int j = s; j<= t; j++)
{
if(qq[j].t == 1)
{
w[qq[j].a] = qq[j].b;
}
}
}
for(int i = 1; i<= q; i++)
{
if(ans[i]) printf("%d\n", ans[i]);
}
}